#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define ff first
#define sc second
vector<int> di = {1, -1, 0, 0}, dj = {0, 0, 1, -1};
int n, m, min_d[4000][4000], ans = 1;
string grid[4000];
int main(){
// freopen("A.IN", "r", stdin);
// freopen("A.OUT", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m; cin >> n >> m;
for(int i = 0; i < n; i++) cin >> grid[i];
min_d[0][0] = 1;
deque<pii> q;
q.push_back({0,0});
while(q.size()){
pii cur = q.front();
q.pop_front();
ans = max(ans, min_d[cur.ff][cur.sc]);
for(int i = 0; i < n; i++){
int ni = cur.ff + di[i];
int nj = cur.sc + dj[i];
if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
if(min_d[ni][nj] != 0 || grid[ni][nj] == '.') continue;
if(grid[cur.ff][cur.sc] == grid[ni][nj]){
min_d[ni][nj] = min_d[cur.ff][cur.sc];
q.push_front({ni, nj});
}
else {
min_d[ni][nj] = min_d[cur.ff][cur.sc] + 1;
q.push_back({ni, nj});
}
}
}
cout << ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
218 ms |
3920 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Correct |
144 ms |
3676 KB |
Output is correct |
| 5 |
Correct |
17 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
856 KB |
Output is correct |
| 10 |
Correct |
13 ms |
1840 KB |
Output is correct |
| 11 |
Correct |
16 ms |
1692 KB |
Output is correct |
| 12 |
Correct |
46 ms |
2092 KB |
Output is correct |
| 13 |
Correct |
12 ms |
2140 KB |
Output is correct |
| 14 |
Correct |
12 ms |
2136 KB |
Output is correct |
| 15 |
Correct |
191 ms |
3724 KB |
Output is correct |
| 16 |
Correct |
231 ms |
3920 KB |
Output is correct |
| 17 |
Correct |
122 ms |
3588 KB |
Output is correct |
| 18 |
Correct |
145 ms |
3664 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
110 ms |
15976 KB |
Output is correct |
| 2 |
Correct |
1421 ms |
11864 KB |
Output is correct |
| 3 |
Execution timed out |
2065 ms |
51792 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2003 ms |
29520 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2066 ms |
32636 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2064 ms |
47704 KB |
Time limit exceeded |
| 7 |
Correct |
100 ms |
16712 KB |
Output is correct |
| 8 |
Correct |
102 ms |
16012 KB |
Output is correct |
| 9 |
Correct |
2 ms |
860 KB |
Output is correct |
| 10 |
Correct |
1 ms |
604 KB |
Output is correct |
| 11 |
Correct |
68 ms |
16424 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1116 KB |
Output is correct |
| 13 |
Correct |
1518 ms |
11912 KB |
Output is correct |
| 14 |
Correct |
617 ms |
8012 KB |
Output is correct |
| 15 |
Correct |
496 ms |
10380 KB |
Output is correct |
| 16 |
Correct |
268 ms |
4860 KB |
Output is correct |
| 17 |
Execution timed out |
2036 ms |
19348 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2017 ms |
24520 KB |
Time limit exceeded |
| 19 |
Correct |
1991 ms |
29444 KB |
Output is correct |
| 20 |
Execution timed out |
2102 ms |
20460 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2029 ms |
34992 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2027 ms |
32684 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2027 ms |
28408 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2080 ms |
33588 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2043 ms |
53756 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2094 ms |
31536 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2017 ms |
37124 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2005 ms |
47628 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2012 ms |
41036 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2087 ms |
42052 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2077 ms |
36692 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2090 ms |
55348 KB |
Time limit exceeded |
