Submission #725606

#	Time	Username	Problem	Language	Result	Execution time	Memory
725606		a_aguilo	Tracks in the Snow (BOI13_tracks)	C++14	47.50 / 100	2089 ms	109156 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

int H, W;
vector<string> snow;
vector<vector<int>> visited;

int bfs(){
	char animal = snow[H-1][W-1];
	queue<pair<int, int>> Q;
	int numNew = 0;
	Q.push({H-1, W-1});
	snow[H-1][W-1] = animal^'F'^'R';
	while(!Q.empty()){
		pair<int, int> actual = Q.front(); Q.pop();
		int x = actual.first;
		int y = actual.second;
		if(!visited[actual.first][actual.second]){
			visited[actual.first][actual.second] = 1;
			numNew++;
		}
		if(x){
			if(snow[x-1][y] == animal){
				snow[x-1][y] = animal^'R'^'F';
				Q.push({x-1, y});
			}
		}
		if(y){
			if(snow[x][y-1] == animal){
				snow[x][y-1] = animal^'R'^'F';
				Q.push({x, y-1});
			}
		}
		if(x < (H-1)){
			if(snow[x+1][y] == animal){
				snow[x+1][y] = animal^'F'^'R';
				Q.push({x+1, y});
			}
		}
		if(y < (W-1)){
			if(snow[x][y+1] == animal){
				snow[x][y+1] = animal^'R'^'F';
				Q.push({x, y+1});
			}
		}
	}
	return numNew;
}

int main(){
	cin >> H >> W;
	visited = vector<vector<int>>(H, vector<int>(W, 0));
	snow = vector<string>(H);
	for(int i = 0; i < H; ++i)cin >> snow[i];
	int ans = 0;
	while(bfs())ans++;
	cout << ans << endl;
	return 0;
}

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