Submission #592987

#	Time	Username	Problem	Language	Result	Execution time	Memory
592987		beaboss	Tracks in the Snow (BOI13_tracks)	C++14	2.19 / 100	889 ms	79264 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
	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 = newx;
			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;


}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:38:19: warning: 'newx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |     if (graph[newx][newy] == '.' || dist[newx][newy] != -1) continue;
      |                   ^

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