Submission #592990

#	Time	Username	Problem	Language	Result	Execution time	Memory
592990		beaboss	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1953 ms	400636 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int h, w;

	cin >> h >> w;

	vector<vector<char> > graph(h, vector<char>(w, 0));

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> graph[i][j];
		}
	}

	deque<vector<int> > bfs;

	bfs.push_back({0, 0});
	vector<vector<int> > dist(h, vector<int>(w, -1));
	dist[0][0] = 1;
	int ans = 0;
	vector<pair<int, int> > vec = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

	while (!bfs.empty()) {
		auto current = bfs.front();
		bfs.pop_front();
		ans = max(ans, dist[current[0]][current[1]]);
		// cout << current[0] << current[1] << dist[current[0]][current[1]] << endl;
		for (pair<int, int> val: vec) {
			int newx = current[0] + val.first;
			int newy = current[1] + val.second;
			if (newx >= 0 &&
				newx < h &&
				newy < w &&
				newy >= 0) {
				if (graph[newx][newy] == '.' || dist[newx][newy] != -1) continue;
				
				if (graph[newx][newy] == 
					graph[current[0]][current[1]]) {
					dist[newx][newy] = dist[current[0]][current[1]];
					bfs.push_front({newx, newy});
				} else {
					bfs.push_back({newx, newy});
					dist[newx][newy] = dist[current[0]][current[1]] + 1;
					
				}
			}
		}
	}

	cout << ans << endl;


}

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