Submission #1235806

#TimeUsernameProblemLanguageResultExecution timeMemory
1235806mihirTracks in the Snow (BOI13_tracks)C++20
100 / 100
478 ms114144 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);	

	int h, w;
	cin >> h >> w;

	vector<string> arr(h);

	for (int i = 0; i < h; ++i) {
		cin >> arr[i];

	}

	deque<pair<int, int>> stk;
	
	char cur_char = arr[0][0];

	stk.push_front({0, 0});

	int cnt = 1;

	while(!stk.empty()) {

		auto [x, y] = stk.front();
		stk.pop_front();

		if (arr[x][y] == '.') {
			continue;
		}
		if (arr[x][y] != cur_char) {
			++cnt;
			cur_char = arr[x][y];
		}

		arr[x][y] = '.';

		int dx[] = {-1, 1, 0, 0};
		int dy[] = {0, 0, -1, 1};

		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= h || ny >= w || nx < 0 || ny < 0 || arr[nx][ny] == '.') {
				continue;
			} else if (arr[nx][ny] == cur_char) {
				stk.push_front({nx, ny});
			} else {
				stk.push_back({nx, ny});
			}
		}
	}

	cout << cnt << endl;

	return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...