Submission #441669

#	Time	Username	Problem	Language	Result	Execution time	Memory
441669		maraam	Tracks in the Snow (BOI13_tracks)	C++17	91.25 / 100	2122 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> ll;

const long long INF = 8020;

const long long MAX_h = 4010;
const long long MAX_w = 4010;

char grid[MAX_h][MAX_w];

long long dist[MAX_h][MAX_w];

long long dr[] = {1, -1, 0, 0};
long long dc[] = {0, 0, 1, -1};

int main() {

	// freopen("tracksinthesnow_in.txt", "r", stdin);

	long long h, w; cin >> h >> w;

	for (long long i = 0; i < h; i++) {
		for (long long j = 0; j < w; j++) {
			cin >> grid[i][j];
		}
	}

	for (long long i = 0; i < h; i++) {
		for (long long j = 0; j < w; j++) {
			dist[i][j] = INF;
		}
	}

	long long ans = 1;

	ll s = ll(0, 0); 

	deque<ll> q; q.push_front(s); dist[s.first][s.second] = 1;

	while (!q.empty()) {

		long long r = q.front().first; long long c = q.front().second; q.pop_front();

		ans = max(ans, dist[r][c]);

		for (long long i = 0; i < 4; i++) {

			long long nr = r + dr[i]; long long nc = c + dc[i];

			if ((nr < 0 || nr >= h || nc < 0 || nc >= w) || grid[nr][nc] == '.') continue;

			if (dist[nr][nc] == INF) {

				if (grid[nr][nc] != grid[r][c]) {
					dist[nr][nc] = dist[r][c] + 1;
					q.push_back(ll(nr, nc));
				}
				if (grid[nr][nc] == grid[r][c]) {
					dist[nr][nc] = dist[r][c];
					q.push_front(ll(nr, nc));
				}

			}

		}

	}

	cout << ans << endl;

	return 0;

}

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