Submission

xxxxPxxx

Score: 13

User: Power2two

Problemset: Sirabyrinth 3

Language: cpp

Time: 0.114 second

Submitted On: 2024-12-13 18:00:06

#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][m];
	int dmap[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>map[i][j];
			dmap[i][j]=-1;
			if(map[i][j]=='S'){
				push(i,j,0);
			}
		}
	}
	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()+1][bfs[1].front()]!=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()+1][bfs[1].front()]!=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()+(map[bfs[0].front()][bfs[1].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;
}