Submission #1310471

#TimeUsernameProblemLanguageResultExecution timeMemory
1310471KarolZTracks in the Snow (BOI13_tracks)C++20
100 / 100
577 ms89148 KiB
#include<iostream>
#include<queue>
using namespace std;
char c[4010][4010];
int czy_odw[4010][4010];
pair<int,int>p[4]={{-1,0},{0,-1},{1,0},{0,1}};
int beefes(int a,int b){
	int kt=1;
	queue< pair<int,int> >q[2];
	q[1].push({a,b});
	czy_odw[a][b]=1;
	while(!q[1].empty()){
		while(!q[1].empty()){
			q[0].push(q[1].front());
			q[1].pop();
		}
		while(!q[0].empty()){
			a=q[0].front().first;
			b=q[0].front().second;
			q[0].pop();
			for(int i=0;i<4;i++){
				int aa=a+p[i].first;
				int bb=b+p[i].second;
				if(czy_odw[aa][bb]==0&&c[aa][bb]!='.'){
					czy_odw[aa][bb]=1;
					q[(c[aa][bb]!=c[a][b])?1:0].push({aa,bb});
				}
			}
		}
		kt++;
	}
	return kt-1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			if(i==0||j==0||i==n+1||j==m+1)c[i][j]='.';
			else cin>>c[i][j];
		}
	}
	cout<<beefes(1,1)<<'\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...