Submission #1280897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280897		m_a_d	Tracks in the Snow (BOI13_tracks)	C++20	19.79 / 100	1576 ms	217520 KiB

tracks

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

#define int long long
#define fi first
#define se second

int32_t main() {
	int n, m;
	cin >> n >> m;
	char grid[n][m];
	vector<vector<int>> distances(n, vector<int>(m, INT32_MAX));

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> grid[i][j];

	vector<pair<int, int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
	distances[0][0] = 0;
	deque<pair<int, int>> que;
	que.push_front({0, 0});

	while (!que.empty()) {
		auto curr = que.front(); que.pop_front();
		for (auto& d : dirs) {
			int nx = curr.fi + d.fi;
			int ny = curr.se + d.se;
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				int w = (grid[curr.fi][curr.se] == grid[nx][ny]) ? 0 : 1;
				if (distances[curr.fi][curr.se] + w < distances[nx][ny]) {
					distances[nx][ny] = distances[curr.fi][curr.se] + w;
					if (w == 1) que.push_back({nx, ny});
					else que.push_front({nx, ny});
				}
			}
		}
	}

	int max_d = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			max_d = max(max_d, distances[i][j]);

	cout << max_d + 1 << '\n';
	return 0;
}

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