Submission #1265198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265198		kwanddwo	Tracks in the Snow (BOI13_tracks)	C++20	16.46 / 100	954 ms	1114112 KiB

tracks

#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};
int x, y, c;
void flood_fill(pair<int, int> curr, queue<pair<int, int>>& q) {
	y = curr.first; 
	x = curr.second;
	if (seen[y][x])
		return;
	seen[y][x] = true;
	for (int i = 0; i < 4; i++) {
		if (y + dy[i] < 0 || y + dy[i] > n - 1)
			continue;
		if (x + dx[i] < 0 || x + dx[i] > m - 1)
			continue;
		if (seen[y + dy[i]][x + dx[i]])
			continue;
		
		c = cmap[y + dy[i]][x + dx[i]];
		if (c == '.')
			continue;
		if (c != currChar) {
			q.push(make_pair(y + dy[i], x + dx[i]));
			continue;
		}
		flood_fill({y + dy[i], x + dx[i]}, 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;
	queue<pair<int, int>> q;
	q.push({0, 0});

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

	cout << changeCount;
}

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