#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 |