Submission #1278995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278995		IBory	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	498 ms	127072 KiB

tracks

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 4004;
char C[MAX][MAX];
int D[MAX][MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) for (int j = 1; j <= M; ++j) cin >> C[i][j];

	int ans = 0;
	memset(D, 0x3f, sizeof(D));
	deque<pii> Q;
	D[1][1] = 1;
	Q.emplace_back(1, 1);
	while (!Q.empty()) {
		auto [y, x] = Q.front(); Q.pop_front();
		ans = D[y][x];
		for (int k = 0; k < 4; ++k) {
			int ny = y + "2101"[k] - '1', nx = x + "1012"[k] - '1';
			if (ny < 1 || nx < 1 || N < ny || M < nx) continue;
			if (C[ny][nx] == '.' || D[ny][nx] < 1e9) continue;
			D[ny][nx] = D[y][x] + (C[y][x] != C[ny][nx]);
			if (D[y][x] == D[ny][nx]) Q.emplace_front(ny, nx);
			else Q.emplace_back(ny, nx);
		}
	}

	cout << ans;
	return 0;
}

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