Submission

xxxxxxxx

Score: 0

User: Power2two

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.110 second

Submitted On: 2024-12-13 19:03:36

#include <bits/stdc++.h>

using namespace std;

queue<int> bfs[3];

void push(int a, int b, int c){
	bfs[0].push(a);
	bfs[1].push(b);
	bfs[2].push(c);
}

int main(int argc, char** argv) {
	
	int n,m,maxx=0;
	cin>>n>>m;
	char map[n+2][m+2];
	int dmap[n+2][m+2];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>map[i][j];
			dmap[i][j]=-1;
			if(map[i][j]=='S'){
				push(i,j,0);
			}
		}
	}
	for(int i=0;i<=n+1;i++){
	    map[i][0]='.';
	    dmap[i][0]=-1;
	}
	for(int i=0;i<=n+1;i++){
	    map[i][m+1]='.';
	    dmap[i][m+1]=-1;
	}
	for(int j=0;j<=n+1;j++){
	    map[0][j]='.';
	    dmap[0][j]=-1;
	}
	for(int j=0;j<=n+1;j++){
	    map[n+1][j]='.';
	    dmap[n+1][j]=-1;
	}
	while(bfs[0].empty()==0){
		if((dmap[bfs[0].front()+1][bfs[1].front()]==-1 || dmap[bfs[0].front()+1][bfs[1].front()]>bfs[2].front()) && dmap[bfs[0].front()+1][bfs[1].front()]!=NULL){
			if(map[bfs[0].front()][bfs[1].front()]!='#'){
				push(bfs[0].front()+1, bfs[1].front(), bfs[2].front());
			}
			else if (map[bfs[0].front()+1][bfs[1].front()]!='#'){
				push(bfs[0].front()+1, bfs[1].front(), bfs[2].front()+1);
			}
			else{
				push(bfs[0].front()+1, bfs[1].front(), bfs[2].front());
			}
		}
		if((dmap[bfs[0].front()][bfs[1].front()+1]==-1 || dmap[bfs[0].front()][bfs[1].front()+1]>bfs[2].front())&& dmap[bfs[0].front()][bfs[1].front()+1]!=NULL){
			if(map[bfs[0].front()][bfs[1].front()]!='#'){
				push(bfs[0].front(), bfs[1].front()+1, bfs[2].front());
			}
			else if (map[bfs[0].front()][bfs[1].front()+1]!='#'){
				push(bfs[0].front(), bfs[1].front()+1, bfs[2].front()+1);
			}
			else{
				push(bfs[0].front(), bfs[1].front()+1, bfs[2].front());
			}
		}
		if((dmap[bfs[0].front()-1][bfs[1].front()]==-1 || dmap[bfs[0].front()-1][bfs[1].front()]>bfs[2].front())&& dmap[bfs[0].front()-1][bfs[1].front()]!=NULL){
			if(map[bfs[0].front()][bfs[1].front()]!='#'){
				push(bfs[0].front()-1, bfs[1].front(), bfs[2].front());
			}
			else if (map[bfs[0].front()-1][bfs[1].front()]!='#'){
				push(bfs[0].front()-1, bfs[1].front(), bfs[2].front()+1);
			}
			else{
				push(bfs[0].front()-1, bfs[1].front(), bfs[2].front());
			}
		}
		if((dmap[bfs[0].front()][bfs[1].front()-1]==-1 || dmap[bfs[0].front()][bfs[1].front()-1]>bfs[2].front())&& dmap[bfs[0].front()][bfs[1].front()-1]!=NULL){
			if(map[bfs[0].front()][bfs[1].front()]!='#'){
				push(bfs[0].front(), bfs[1].front()-1, bfs[2].front());
			}
			else if (map[bfs[0].front()][bfs[1].front()-1]!='#'){
				push(bfs[0].front(), bfs[1].front()-1, bfs[2].front()+1);
			}
			else{
				push(bfs[0].front(), bfs[1].front()-1, bfs[2].front());
			}
		}
		if(bfs[2].front()>maxx){
			maxx=bfs[2].front();
		}
		dmap[bfs[0].front()][bfs[1].front()]=bfs[2].front();
		bfs[0].pop();
		bfs[1].pop();
		bfs[2].pop();
	}
	cout<<maxx;
}