Submission #1077141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077141		ssitaram	Tracks in the Snow (BOI13_tracks)	C++17	19.79 / 100	1157 ms	400664 KiB

tracks

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

const vector<int> dx = {-1, 1, 0, 0},
	  dy = {0, 0, -1, 1};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int h, w; cin >> h >> w;
	vector<string> grid(h);
	for (string& s : grid) cin >> s;
	deque<pair<int, pair<int, int>>> dq;
	dq.push_front({1, {0, 0}});
	vector<vector<bool>> vis(h, vector<bool>(w));
	int ans = 1;
	while (!dq.empty()) {
		int d = dq.front().first;
		pair<int, int> pla = dq.front().second;
		dq.pop_front();
		if (vis[pla.first][pla.second]) continue;
		vis[pla.first][pla.second] = true;
		ans = max(ans, d);
		for (int i = 0; i < 4; ++i) {
			pair<int, int> ne = {pla.first + dx[i], pla.second + dy[i]};
			if (ne.first < 0 || ne.first >= h || ne.second < 0 || ne.second >= w) continue;
			if (grid[pla.first][pla.second] == grid[ne.first][ne.second]) {
				dq.push_front({d, ne});
			} else {
				dq.push_back({d + 1, ne});
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

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