Submission #727407

#	Time	Username	Problem	Language	Result	Execution time	Memory
727407		a_aguilo	Tracks in the Snow (BOI13_tracks)	C++14	82.50 / 100	2088 ms	190860 KiB

tracks

#include<bits/stdc++.h>

using namespace std;

int H, W;
vector<string> snow;

int dijkstra(){
	vector<int> distances(H*W, -1);
	int maxDist = 0;
	priority_queue<vector<int>> PQ;
	PQ.push({0, 0, 0});
	while(!PQ.empty()){
		vector<int> act = PQ.top(); PQ.pop();
		int x = act[1];
		int y = act[2];
		int d = -act[0];
		int position = x*W + y;

		if(distances[position] != -1) continue;
		distances[position] = d;
		maxDist = max(maxDist, d);
		if(x){
			int nextPos = (x-1)*W + y;
			if(distances[nextPos] == -1){
				if(snow[x-1][y] == snow[x][y])PQ.push({-d, x-1, y});
				else if (snow[x-1][y] != '.') PQ.push({-d-1, x-1, y});
			}
		}
		if(y){
			int nextPos = x*W + y - 1;
			if(distances[nextPos] == -1){
				if(snow[x][y-1] == snow[x][y]) PQ.push({-d, x, y-1});
				else if(snow[x][y-1] != '.') PQ.push({-d-1, x, y-1});
			}
		}
		if(x < (H-1)){
			int nextPos = (x+1)*W + y;
			if(distances[nextPos] == -1){
				if(snow[x+1][y] == snow[x][y])PQ.push({-d, x+1, y});
				else if(snow[x+1][y] != '.') PQ.push({-d-1, x+1, y});
			}
		}
		if(y < (W-1)){
			int nextPos = x*W + y + 1;
			if(distances[nextPos] == -1){
				if(snow[x][y+1] == snow[x][y]) PQ.push({-d, x, y+1});
				else if (snow[x][y+1] != '.') PQ.push({-d-1, x, y+1});
			}
		}
	}
	return maxDist;
}

int main(){
	cin >> H >> W;
	snow = vector<string>(H);
	for(int i = 0; i < H; ++i)cin >> snow[i];
	
	cout << dijkstra()+1 << endl;
	return 0;
}

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