Submission #121865

#	Time	Username	Problem	Language	Result	Execution time	Memory
121865		Adhyyan1252	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	595 ms	90484 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

vector<vector<char> > g;
int h, w; 

using ii = pair<int, int>;


int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>h>>w;
	g = vector<vector<char> >(h, vector<char>(w));
	for(int i = 0; i < h; i++){
		string inp; cin>>inp;
		for(int j = 0; j < w; j++){
			if(inp[j] == '.'){
				g[i][j] = 2;
			}else if(inp[j] == 'F'){
				g[i][j] = 0;
			}else if(inp[j] == 'R'){
				g[i][j] = 1;
			}
		}
	}
	if(g[0][0] == 2){
		cout<<0<<endl;
		return 0;
	}

	if(g[0][0] != 0){ //flip if first one is 1
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(g[i][j] != 2) g[i][j] = 1 - g[i][j];
			}
		}
	}
	
	//top left cell is now 0
	vector<ii> active;
	active.push_back({0, 0});
	int ans = 0;
	g[0][0] = 3;
	vector<ii> del = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	while(!active.empty()){
		//cout<<"ANS "<<ans<<endl;
		vector<ii> nact;
		while(!active.empty()){
			int x = active.back().first, y = active.back().second;
			//cout<<"CUR "<<x<<" "<<y<<endl;
			active.pop_back();
			for(ii vec: del){
				int xd = x + vec.first, yd = y + vec.second;
				if(xd < 0 || xd >= h || yd < 0 || yd >= w) continue;
				//cout<<"CHECKING "<<xd<<" "<<yd<<" "<<(int)g[xd][yd]<<endl;
				if(g[xd][yd] == 3){ // means its visited
					
				}else if(g[xd][yd] == 2){ //empty
					
				}else if(g[xd][yd] == (ans%2)){
					active.push_back({xd, yd});
					//cout<<"PUSHED "<<xd<<" "<<yd<<endl;
					g[xd][yd] = 3;
				}else{
					nact.push_back({xd, yd});
					//cout<<"PUSHED D"<<xd<<" "<<yd<<endl;
					g[xd][yd] = 3;
				}
			}
		}
//		for(ii cur: nact){
//			cout<<"NACT "<<cur.first<<" "<<cur.second<<endl;
//		}
		ans++;
		active = nact; 
		nact.clear();
	}
	cout<<ans<<endl;
}

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