Submission #747074

#	Time	Username	Problem	Language	Result	Execution time	Memory
747074		LCJLY	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1078 ms	66652 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int n,m;
	cin >> n >> m;
	
	string arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	queue<pii>q;
	queue<pii>q2;
	int counter=0;
	bool visited[n+5][m+5];
	memset(visited,0,sizeof(visited));
	
	bool amos=true;
	//true is R, false is F
	if(arr[0][0]=='F') amos=false;
	if(amos){
		q.push({0,0});
		visited[0][0]=true;
	}
	else{
		q2.push({0,0});
		visited[0][0]=true;
	}	
	
	pii dir[4]={
		{1,0},
		{-1,0},
		{0,1},
		{0,-1},
	};
	
	while(!q.empty()||!q2.empty()){
		if(amos){
			//cout << "true\n";
			while(!q.empty()){
				pii cur=q.front();
				q.pop();
				
				for(auto it:dir){
					int newx=cur.first+it.first;
					int newy=cur.second+it.second;
					if(newx<0||newy<0||newx>=n||newy>=m) continue;
					if(visited[newx][newy]) continue;
					if(arr[newx][newy]=='.') continue;
					visited[newx][newy]=true;
					if(arr[newx][newy]=='R'){
						q.push({newx,newy});
					}
					else{
						q2.push({newx,newy});
					}
				}	
			}
			amos=false;
		}
		else{
			//cout << "false\n";
			while(!q2.empty()){
				pii cur=q2.front();
				q2.pop();
				//cout << cur.first << " " << cur.second << " visit\n";
				for(auto it:dir){
					int newx=cur.first+it.first;
					int newy=cur.second+it.second;
					if(newx<0||newy<0||newx>=n||newy>=m) continue;
					if(visited[newx][newy]) continue;
					if(arr[newx][newy]=='.') continue;
					visited[newx][newy]=true;
					if(arr[newx][newy]=='R'){
						q.push({newx,newy});
					} 
					else{
						q2.push({newx,newy});
					}
				}	
			}
			amos=true;
		}
		counter++;
		//cout << counter << "\n";
	}
	cout << counter;
}

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