Submission #517766

#	Time	Username	Problem	Language	Result	Execution time	Memory
517766		Jomnoi	Tracks in the Snow (BOI13_tracks)	C++17	31.77 / 100	2103 ms	94956 KiB

tracks

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 4e3 + 10;
const int INF = 1e9 + 7;
const int r[] = {-1, 0, 1, 0};
const int c[] = {0, -1, 0, 1};

char a[N][N];
int dist[N][N];

int main() {
	cin.tie(0)->sync_with_stdio(0);
    int h, w;
    cin >> h >> w;
	for(int i = 1; i <= h; i++) {
		for(int j = 1; j <= w; j++) {
			dist[i][j] = INF;
		}
	}
    for(int i = 1; i <= h; i++) {
        cin >> (a[i] + 1);
    }

	int ans = 0;
	deque <pair <int, int>> dq;
	dq.emplace_back(1, 1);
	dist[1][1] = 1;
	while(!dq.empty()) {
		auto [xi, yi] = dq.front();
		dq.pop_front();

		ans = max(ans, dist[xi][yi]);
		for(int d = 0; d < 4; d++) {
			int xj = xi + r[d], yj = yi + c[d];
			if(xj < 1 or xj > h or yj < 1 or yj > w or a[xj][yj] == '.') {
				continue;
			}

			int w = (a[xi][yi] != a[xj][yj]);
			if(dist[xi][yi] + w < dist[xj][yj]) {
				dist[xj][yj] = dist[xi][yi] + w;
				dq.emplace_back(xj, yj);
			}
		}
	}
	cout << ans;
	return 0;
}

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