Submission #999966

#	Time	Username	Problem	Language	Result	Execution time	Memory
999966		Dipa	Tracks in the Snow (BOI13_tracks)	C++14	80.31 / 100	2102 ms	97244 KiB

tracks

#include <bits/stdc++.h>
#define INF_INT 2147483647
#define what_is(x) cerr << #x << " is " << x << endl;
#define all(v) v.begin(), v.end()
typedef long long ll;
using namespace std;

void solve() {
	int H, W; cin >> H >> W;

	string grid[H];
	for (auto &el: grid) cin >> el;

	vector<vector<int>> dist(H, vector<int>(W, 1e9));
	deque<pair<int, int>> dq;
	dq.push_back({0, 0});
	dist[0][0] = 0;

	while (!dq.empty()) {
		pair<int, int> current = dq.front();
		dq.pop_front();

		// go down
		if (current.first + 1 < H && (grid[current.first + 1][current.second] != '.')) {
			if (grid[current.first + 1][current.second] != grid[current.first][current.second]) {
				if (dist[current.first + 1][current.second] > dist[current.first][current.second] + 1) {
					dist[current.first + 1][current.second] = dist[current.first][current.second] + 1;
					dq.push_back({current.first + 1, current.second});
				}
			} else {
				if (dist[current.first + 1][current.second] > dist[current.first][current.second]) {
					dist[current.first + 1][current.second] = dist[current.first][current.second];
					dq.push_back({current.first + 1, current.second});
				}
			}
		}

		// go left
		// cout << "UP" << endl;

		if (current.second - 1 >= 0 && grid[current.first][current.second - 1] != '.') {

			if (grid[current.first][current.second - 1] != grid[current.first][current.second]) {
				if (dist[current.first][current.second - 1] > dist[current.first][current.second] + 1) {
					dist[current.first][current.second - 1] = dist[current.first][current.second] + 1;
					dq.push_back({current.first, current.second - 1});
				}
			} else {
				if (dist[current.first][current.second - 1] > dist[current.first][current.second]) {
					dist[current.first][current.second - 1] = dist[current.first][current.second];
					dq.push_back({current.first, current.second - 1});
				}
			}
		}

		// go right
		if (current.second + 1 < W && grid[current.first][current.second + 1] != '.') {

			if (grid[current.first][current.second + 1] != grid[current.first][current.second]) {
				if (dist[current.first][current.second + 1] > dist[current.first][current.second] + 1) {
					dist[current.first][current.second + 1] = dist[current.first][current.second] + 1;
					dq.push_back({current.first, current.second + 1});
				}
			} else {
				if (dist[current.first][current.second + 1] > dist[current.first][current.second]) {
					dist[current.first][current.second + 1] = dist[current.first][current.second];
					dq.push_back({current.first, current.second + 1});
				}
			}
		}

		// go up
		if (current.first - 1 >= 0 && grid[current.first - 1][current.second] != '.') {

			if (grid[current.first - 1][current.second] != grid[current.first][current.second]) {
				if (dist[current.first - 1][current.second] > dist[current.first][current.second] + 1) {
					dist[current.first - 1][current.second] = dist[current.first][current.second] + 1;
					dq.push_back({current.first - 1, current.second});
				}
			} else {
				if (dist[current.first - 1][current.second] > dist[current.first][current.second]) {
					dist[current.first - 1][current.second] = dist[current.first][current.second];
					dq.push_back({current.first - 1, current.second});
				}
			}
		}
	}

	int ans = -1;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (dist[i][j] != (int) 1e9) ans = max(ans, dist[i][j]);
		}
	}

	cout << ans + 1 << '\n';
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

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