Submission #1265210

#TimeUsernameProblemLanguageResultExecution timeMemory
1265210kwanddwoTracks in the Snow (BOI13_tracks)C++20
97.81 / 100
833 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;

char cmap[4000][4000];
bool seen[4000][4000];
int n, m;

char currChar;
int changeCount = 1;

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

void flood_fill(pair<int, int> curr, deque<pair<int, int>>& q) {
	int y = curr.first, x = curr.second;
	if (seen[y][x])
		return;

	seen[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int nextY = y + dy[i];
		int nextX = x + dx[i]; 	
		if (nextY < 0 || nextY > n - 1)
			continue;
		if (nextX < 0 || nextX > m - 1)
			continue;
		if (seen[nextY][nextX])
			continue;
		
		char c = cmap[nextY][nextX];
		if (c == '.')
			continue;
		if (c != currChar) {
			q.push_back(make_pair(nextY, nextX));
			continue;
		}
		flood_fill(make_pair(nextY, nextX), q);
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> cmap[i][j];
		}
	}

	currChar = cmap[0][0];
	pair<int, int> curr;
	deque<pair<int, int>> q;
	q.push_back({0, 0});

	while (!q.empty()) {
		curr = q.front();
		if (seen[curr.first][curr.second]) {
			q.pop_front();
			continue;
		}
		if (cmap[curr.first][curr.second] != currChar) {
			changeCount++;
			currChar = cmap[curr.first][curr.second];
		}
		flood_fill(curr, q);
		q.pop_front();
	}

	cout << changeCount << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...