Submission #1185142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185142		prism7k	Tracks in the Snow (BOI13_tracks)	C++20	80.21 / 100	1044 ms	119036 KiB

tracks

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

char grid[4000][4000];
int dist[4000][4000];
vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int main() {
	int h, w; cin >> h >> w;
	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
			cin >> grid[i][j];
		}
	}
	function<bool(int, int)> valid = [&](int y, int x) {
		return (y >= 0 && y < h && x >= 0 && x <= w);
	};
	int ans = 0;
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dist[0][0] = 1;
	while(!q.empty()) {
		int y = q.front().first, x = q.front().second;
		q.pop_front();
		ans = max(ans, dist[y][x]);
		
		for(auto dir : dirs) {
			int dy = y + dir.first;
			int dx = x + dir.second;
			if(!valid(dy, dx)) continue;
			
			if(dist[dy][dx] != 0 || grid[dy][dx] == '.') continue;
			if(grid[dy][dx] != grid[y][x]) {
				dist[dy][dx] = dist[y][x] + 1;
				q.push_back({dy, dx});
			} else {
				dist[dy][dx] = dist[y][x];
				q.push_front({dy, dx});
			}
		}
	}
	cout << ans << "\n";
}

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