#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define mp mka
string s[4005];
short int dist[4005][4005];
deque<pair<int, int> > dq;
int h , w;
int dx[4] = { 0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
cin>>h>>w;
for(int i = 0 ; i < h ; i ++){
cin>>s[i];
for(int j = 0 ; j < w ; j ++){
dist[i][j] = numeric_limits<short>::max();
}
}
dq.push_back(pair<int,int>(0,0));
int ans = 0;
dist[0][0] = 0;
while(!dq.empty()){
pii u = dq.front();
ans = max(ans , dist[u.first][u.second]+1);
dq.pop_front();
for(int i = 0 ; i < 4 ; i++){
int x = u.first + dx[i] , y = u.second + dy[i];
if(x >= 0 && y >= 0 && x < h && y < w){
if(s[x][y] != s[u.first][u.second] && s[x][y] != '.' && dist[x][y] > (dist[u.first][u.second] + 1)){
dist[x][y] = dist[u.first][u.second] + 1;
dq.push_back(pair<int,int>(x,y));
}
else{
if(s[x][y] == s[u.first][u.second] && dist[x][y] > (dist[u.first][u.second])){
dist[x][y] = dist[u.first][u.second];
dq.push_front(pair<int,int>(x,y));
}
}
}
}
}
cout<<ans<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
3448 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
3 ms |
760 KB |
Output is correct |
| 4 |
Correct |
11 ms |
3320 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1912 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
3 ms |
760 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
5 ms |
1656 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1532 KB |
Output is correct |
| 12 |
Correct |
8 ms |
2040 KB |
Output is correct |
| 13 |
Correct |
5 ms |
2040 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1976 KB |
Output is correct |
| 15 |
Correct |
16 ms |
3448 KB |
Output is correct |
| 16 |
Correct |
19 ms |
3448 KB |
Output is correct |
| 17 |
Correct |
12 ms |
3320 KB |
Output is correct |
| 18 |
Correct |
10 ms |
3320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
53 ms |
11660 KB |
Output is correct |
| 3 |
Incorrect |
89 ms |
65168 KB |
Output isn't correct |
| 4 |
Correct |
69 ms |
22904 KB |
Output is correct |
| 5 |
Incorrect |
52 ms |
42488 KB |
Output isn't correct |
| 6 |
Correct |
739 ms |
79660 KB |
Output is correct |
| 7 |
Correct |
15 ms |
16632 KB |
Output is correct |
| 8 |
Correct |
14 ms |
15992 KB |
Output is correct |
| 9 |
Correct |
4 ms |
760 KB |
Output is correct |
| 10 |
Correct |
2 ms |
632 KB |
Output is correct |
| 11 |
Correct |
14 ms |
16376 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 13 |
Correct |
53 ms |
11796 KB |
Output is correct |
| 14 |
Correct |
35 ms |
7644 KB |
Output is correct |
| 15 |
Incorrect |
13 ms |
8440 KB |
Output isn't correct |
| 16 |
Correct |
29 ms |
4680 KB |
Output is correct |
| 17 |
Correct |
133 ms |
24544 KB |
Output is correct |
| 18 |
Incorrect |
31 ms |
24184 KB |
Output isn't correct |
| 19 |
Correct |
70 ms |
22776 KB |
Output is correct |
| 20 |
Incorrect |
35 ms |
21184 KB |
Output isn't correct |
| 21 |
Incorrect |
62 ms |
43896 KB |
Output isn't correct |
| 22 |
Incorrect |
53 ms |
42440 KB |
Output isn't correct |
| 23 |
Correct |
256 ms |
36088 KB |
Output is correct |
| 24 |
Incorrect |
61 ms |
43512 KB |
Output isn't correct |
| 25 |
Incorrect |
97 ms |
65144 KB |
Output isn't correct |
| 26 |
Correct |
624 ms |
103588 KB |
Output is correct |
| 27 |
Correct |
596 ms |
90700 KB |
Output is correct |
| 28 |
Correct |
759 ms |
79636 KB |
Output is correct |
| 29 |
Correct |
706 ms |
76932 KB |
Output is correct |
| 30 |
Correct |
694 ms |
82580 KB |
Output is correct |
| 31 |
Correct |
676 ms |
47216 KB |
Output is correct |
| 32 |
Correct |
591 ms |
89244 KB |
Output is correct |
