Submission #1256659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256659		kerem	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1284 ms	176352 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;



void solve(){
	int n,m;
	cin >> n >> m;
	char a[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> a[i][j];
			if(a[i][j]=='F') a[i][j]=0;
			if(a[i][j]=='R') a[i][j]=1;
			if(a[i][j]=='.') a[i][j]=2;
		}
	}
	queue<pii> p,q;
	q.push({0,0});
	int vis[n][m],c=a[0][0],ans=0;
	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		while(!q.empty()){
			int x=q.front().fr,y=q.front().sc;
			q.pop();
			if(vis[x][y]) continue;
			vis[x][y]=1;
			if(x!=n-1 && a[x+1][y]==c && !vis[x+1][y])  q.push({x+1,y});
			if(x!=0 && a[x-1][y]==c && !vis[x-1][y]) q.push({x-1,y});
			if(y!=m-1 && a[x][y+1]==c && !vis[x][y+1]) q.push({x,y+1});
			if(y!=0 && a[x][y-1]==c && !vis[x][y-1]) q.push({x,y-1});
			
			if(x!=n-1 && a[x+1][y]==(c^1) && !vis[x+1][y])  p.push({x+1,y});
			if(x!=0 && a[x-1][y]==(c^1) && !vis[x-1][y]) p.push({x-1,y});
			if(y!=m-1 && a[x][y+1]==(c^1) && !vis[x][y+1]) p.push({x,y+1});
			if(y!=0 && a[x][y-1]==(c^1) && !vis[x][y-1]) p.push({x,y-1});
		}
		swap(p,q);
		c^=1;
		ans++;
	}
	cout << ans << endl;
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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