Submission #952343

#	Time	Username	Problem	Language	Result	Execution time	Memory
952343		karpatka	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	503 ms	124260 KiB

tracks

#include <bits/stdc++.h>

using i64 = long long;

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

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

	int h, w;
	std::cin >> h >> w;

	std::vector<std::string> a(h);
	for (int i = 0; i < h; i++) {
		std::cin >> a[i];
	}

	auto valid = [&](int x, int y) {
		return 0 <= x && x < h && 0 <= y && y < w && a[x][y] != '.';
	};

	std::vector dist(h, std::vector<int>(w));
	dist[0][0] = 1;

	int ans = 0;
	std::deque<std::pair<int, int>> que;
	que.emplace_front(0, 0);
	while (!que.empty()) {
		auto [x, y] = que.front();
		que.pop_front();
		ans = std::max(ans, dist[x][y]);

		for (int k = 0; k < 4; k++) {
			int x1 = x + dx[k], y1 = y + dy[k];
			if (valid(x1, y1) && !dist[x1][y1]) {
				if (a[x][y] == a[x1][y1]) {
					dist[x1][y1] = dist[x][y];
					que.emplace_front(x1, y1);
				} else {
					dist[x1][y1] = dist[x][y] + 1;
					que.emplace_back(x1, y1);
				}
			}
		}
	}

	std::cout << ans << '\n';

	return 0;
}

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