Submission #730175

# Submission time Handle Problem Language Result Execution time Memory
730175 2023-04-25T11:33:32 Z a_aguilo Tracks in the Snow (BOI13_tracks) C++14
100 / 100
790 ms 123184 KB
#include<bits/stdc++.h>

using namespace std;

int H, W;
vector<string> snow;
vector<vector<int>> distances;

int bfs(){
	deque<int> DQ;
	distances[0][0] = 1;
	int ans = 1;
	DQ.push_back(0);
	while(!DQ.empty()){
		int actual = DQ.front(); DQ.pop_front();
		int x = actual/W;
		int y = actual - W*x;
		ans = max(ans, distances[x][y]);
		if(x){
			if(distances[x-1][y] == -1){
				if(snow[x-1][y] == snow[x][y]){
					distances[x-1][y] = distances[x][y];
					DQ.push_front((x-1)*W + y);
				}
				else if (snow[x-1][y] != '.'){
					distances[x-1][y] = distances[x][y]+1;
					DQ.push_back((x-1)*W + y);
				}
			}
		}
		if(y){
			if(distances[x][y-1] == -1){
				if(snow[x][y-1] == snow[x][y]){
					distances[x][y-1] = distances[x][y];
					DQ.push_front((x)*W + y-1);
				}
				else if (snow[x][y-1] != '.'){
					distances[x][y-1] = distances[x][y]+1;
					DQ.push_back((x)*W + y-1);
				}
			}
		}
		if(x < (H-1)){
			if(distances[x+1][y] == -1){
				if(snow[x+1][y] == snow[x][y]){
					distances[x+1][y] = distances[x][y];
					DQ.push_front((x+1)*W + y);
				}
				else if (snow[x+1][y] != '.'){
					distances[x+1][y] = distances[x][y]+1;
					DQ.push_back((x+1)*W + y);
				}
			}
		}
		if(y < (W-1)){
			if(distances[x][y+1] == -1){
				if(snow[x][y+1] == snow[x][y]){
					distances[x][y+1] = distances[x][y];
					DQ.push_front((x)*W + y + 1);
				}
				else if (snow[x][y+1] != '.'){
					distances[x][y+1] = distances[x][y]+1;
					DQ.push_back((x)*W + y + 1);
				}
			}
		}
	}
	return ans;
}

int main(){
	cin >> H >> W;
	snow = vector<string>(H);
	for(int i = 0; i < H; ++i)cin >> snow[i];
	distances = vector<vector<int>>(H, vector<int>(W, -1));
	cout << bfs()<< endl;
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 13 ms 2004 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 11 ms 1336 KB Output is correct
5 Correct 4 ms 836 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 692 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 792 KB Output is correct
13 Correct 4 ms 792 KB Output is correct
14 Correct 4 ms 792 KB Output is correct
15 Correct 16 ms 2024 KB Output is correct
16 Correct 14 ms 2004 KB Output is correct
17 Correct 11 ms 1876 KB Output is correct
18 Correct 9 ms 1364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 60 ms 10376 KB Output is correct
3 Correct 489 ms 108872 KB Output is correct
4 Correct 116 ms 25872 KB Output is correct
5 Correct 299 ms 55844 KB Output is correct
6 Correct 762 ms 115836 KB Output is correct
7 Correct 3 ms 692 KB Output is correct
8 Correct 3 ms 692 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 61 ms 10376 KB Output is correct
14 Correct 34 ms 6448 KB Output is correct
15 Correct 31 ms 7044 KB Output is correct
16 Correct 27 ms 4148 KB Output is correct
17 Correct 150 ms 27860 KB Output is correct
18 Correct 131 ms 27544 KB Output is correct
19 Correct 124 ms 25800 KB Output is correct
20 Correct 102 ms 23856 KB Output is correct
21 Correct 278 ms 57668 KB Output is correct
22 Correct 296 ms 55844 KB Output is correct
23 Correct 311 ms 47876 KB Output is correct
24 Correct 286 ms 56712 KB Output is correct
25 Correct 559 ms 108956 KB Output is correct
26 Correct 499 ms 98824 KB Output is correct
27 Correct 720 ms 123184 KB Output is correct
28 Correct 790 ms 115868 KB Output is correct
29 Correct 764 ms 116172 KB Output is correct
30 Correct 719 ms 116984 KB Output is correct
31 Correct 587 ms 62796 KB Output is correct
32 Correct 653 ms 118132 KB Output is correct