Submission #1119807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119807		buzdi	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1127 ms	409668 KiB

tracks

#include <iostream>
#include <cassert>
#include <cstring>
#include <queue>
#define ll long long

using namespace std;

const int NMAX = 4000;
const int di[] = { 0, 0, 1, -1 };
const int dj[] = { 1, -1, 0, 0 };

struct Triplet {
	int i, j, k;
};

int n, m, answer;
char a[NMAX + 1][NMAX + 1];
char done[NMAX + 1][NMAX + 1];
deque<Triplet> dq;

bool InMat(int i, int j) {
	return i >= 1 && i <= n && j >= 1 && j <= m;
}

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

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

	dq.push_back({1, 1, 1});
	while (!dq.empty()) {
		auto [i, j, k] = dq.back();
		dq.pop_back();

		if (!done[i][j]) {
			done[i][j] = 1;
			answer = max(answer, k);

			for (int d = 0; d < 4; d++) {
				int inou = i + di[d];
				int jnou = j + dj[d];
				if (InMat(inou, jnou) && a[inou][jnou] != '.') {
					if (a[inou][jnou] == a[i][j]) {
						dq.push_back({ inou, jnou, k });
					}
					else {
						dq.push_front({ inou, jnou, k + 1 });
					}
				}
			}
		}
	}
	cout << answer << '\n';

	return 0;
}

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