Submission #1091666

#TimeUsernameProblemLanguageResultExecution timeMemory
1091666ef10Tracks in the Snow (BOI13_tracks)C++17
100 / 100
616 ms90728 KiB
// Source: https://usaco.guide/general/io

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

int H, W;
string M[4005];
bool v[4005][4005];

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> M[i];
	}
	if (M[0][0] == '.') return 0;
	deque<pair<int,int> > q;
	q.push_back(make_pair(0,0));
	v[0][0] = true;
	int res = 1;
	char current = M[0][0];
	while (!q.empty()) {
		auto c = q.front();
		q.pop_front();
		if (M[c.first][c.second] != current) {
			res++;
			current = M[c.first][c.second];
		}
		for (auto i : {-1,1}) {
			for (auto j : {0,1}) {
				if (j==0) {
					if (((i < 0 && c.first > 0) || (i > 0 && c.first < H-1)) && !v[c.first+i][c.second] && M[c.first+i][c.second] != '.') {
						v[c.first+i][c.second] = true;
						if (M[c.first][c.second] == M[c.first+i][c.second]) {
							q.push_front(make_pair(c.first+i,c.second));
						} else {
							q.push_back(make_pair(c.first+i,c.second));
						}
					}
				} else {
					if (((i < 0 && c.second > 0) || (i > 0 && c.second < W-1)) && !v[c.first][c.second+i] && M[c.first][c.second+i] != '.') {
						v[c.first][c.second+i] = true;
						if (M[c.first][c.second] == M[c.first][c.second+i]) {
							q.push_front(make_pair(c.first,c.second+i));
						} else {
							q.push_back(make_pair(c.first,c.second+i));
						}
					}
				}
			}
		}
	}
	cout << res << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...