Submission #1310471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310471		KarolZ	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	577 ms	89148 KiB

tracks

#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;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70