#include <bits/stdc++.h>
using namespace std;
int H, W;
int dx[4]{-1, 1, 0, 0}, dy[4]{0, 0, -1, 1};
char grid[4000][4000];
int lvls[4000][4000];
bool good(int r, int c){
if(r<0 || r>=H || c<0 || c>=W || lvls[r][c]!=0 || grid[r][c]=='.') return false;
return true;
}
int main() {
//# of F connected componetntes + 1 or # of R compoentns + 1
cin >> H >> W;
for (int r=0; r<H; r++){
for (int c=0; c<W; c++){
cin >> grid[r][c];
}
}
deque<pair<int, int>> dq;
dq.push_back({0, 0});
lvls[0][0]=1;
int ans = 1;
while(!dq.empty()){
int x, y;
tie(x, y) = dq.front();
dq.pop_front();
ans = max(ans, lvls[x][y]);
for (int i=0; i<4; i++){
int xnew = x+dx[i]; int ynew = y+dy[i];
if(!good(xnew, ynew)) continue;
if(grid[xnew][ynew]==grid[x][y]){
lvls[xnew][ynew]=lvls[x][y];
dq.push_front({xnew, ynew});
}
else{
lvls[xnew][ynew]=1+lvls[x][y];
dq.push_back({xnew, ynew});
}
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
15 ms |
4976 KB |
Output is correct |
| 5 |
Correct |
9 ms |
2860 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1032 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2388 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2004 KB |
Output is correct |
| 12 |
Correct |
11 ms |
2968 KB |
Output is correct |
| 13 |
Correct |
7 ms |
2772 KB |
Output is correct |
| 14 |
Correct |
7 ms |
2772 KB |
Output is correct |
| 15 |
Correct |
24 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
24 ms |
5188 KB |
Output is correct |
| 17 |
Correct |
20 ms |
4928 KB |
Output is correct |
| 18 |
Correct |
17 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
30852 KB |
Output is correct |
| 2 |
Correct |
124 ms |
13524 KB |
Output is correct |
| 3 |
Correct |
1006 ms |
57572 KB |
Output is correct |
| 4 |
Correct |
261 ms |
28936 KB |
Output is correct |
| 5 |
Correct |
615 ms |
44332 KB |
Output is correct |
| 6 |
Correct |
1418 ms |
91804 KB |
Output is correct |
| 7 |
Correct |
20 ms |
32468 KB |
Output is correct |
| 8 |
Correct |
19 ms |
30932 KB |
Output is correct |
| 9 |
Correct |
5 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
| 11 |
Correct |
17 ms |
31428 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
115 ms |
13520 KB |
Output is correct |
| 14 |
Correct |
70 ms |
9548 KB |
Output is correct |
| 15 |
Correct |
71 ms |
11976 KB |
Output is correct |
| 16 |
Correct |
50 ms |
5040 KB |
Output is correct |
| 17 |
Correct |
326 ms |
24648 KB |
Output is correct |
| 18 |
Correct |
297 ms |
31888 KB |
Output is correct |
| 19 |
Correct |
256 ms |
28944 KB |
Output is correct |
| 20 |
Correct |
248 ms |
22020 KB |
Output is correct |
| 21 |
Correct |
605 ms |
43564 KB |
Output is correct |
| 22 |
Correct |
652 ms |
44416 KB |
Output is correct |
| 23 |
Correct |
620 ms |
36172 KB |
Output is correct |
| 24 |
Correct |
625 ms |
40652 KB |
Output is correct |
| 25 |
Correct |
1193 ms |
78432 KB |
Output is correct |
| 26 |
Correct |
1045 ms |
118984 KB |
Output is correct |
| 27 |
Correct |
1299 ms |
95996 KB |
Output is correct |
| 28 |
Correct |
1390 ms |
91804 KB |
Output is correct |
| 29 |
Correct |
1384 ms |
92092 KB |
Output is correct |
| 30 |
Correct |
1348 ms |
91484 KB |
Output is correct |
| 31 |
Correct |
984 ms |
63308 KB |
Output is correct |
| 32 |
Correct |
1243 ms |
93260 KB |
Output is correct |
