#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
char grid[n][m];
ll dist[n][m];
int visited[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> grid[i][j];
dist[i][j] = 1e18;
visited[i][j] = 0;
}
}
deque<pair<int, int>> q;
dist[0][0] = 0;
q.push_back({0, 0});
vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
while (!q.empty()){
auto x = q.front();
q.pop_back();
if (visited[x.first][x.second]) continue;
visited[x.first][x.second] = 1;
for (auto y : dir){
int nx = x.first + y.first;
int ny = x.second + y.second;
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (grid[nx][ny] == '.') continue;
int d = grid[nx][ny] == grid[x.first][x.second] ? 0 : 1;
if (dist[nx][ny] > (d+dist[x.first][x.second])){
dist[nx][ny] = d+dist[x.first][x.second];
if (d == 0){
q.push_front({nx, ny});
}else{
q.push_back({nx, ny});
}
}
}
}
ll ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (dist[i][j] == 1e18) continue;
ans = max(ans, dist[i][j]);
}
}
cout << (ans+1) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3748 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
2556 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
464 KB |
Output isn't correct |
| 7 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
1628 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
1372 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
3796 KB |
Output isn't correct |
| 16 |
Incorrect |
4 ms |
3676 KB |
Output isn't correct |
| 17 |
Incorrect |
4 ms |
3536 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 2 |
Incorrect |
23 ms |
21852 KB |
Output isn't correct |
| 3 |
Incorrect |
235 ms |
219576 KB |
Output isn't correct |
| 4 |
Incorrect |
55 ms |
51536 KB |
Output isn't correct |
| 5 |
Incorrect |
131 ms |
123476 KB |
Output isn't correct |
| 6 |
Incorrect |
244 ms |
219476 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 13 |
Incorrect |
23 ms |
21848 KB |
Output isn't correct |
| 14 |
Incorrect |
15 ms |
12636 KB |
Output isn't correct |
| 15 |
Incorrect |
15 ms |
13948 KB |
Output isn't correct |
| 16 |
Incorrect |
10 ms |
9052 KB |
Output isn't correct |
| 17 |
Incorrect |
66 ms |
56400 KB |
Output isn't correct |
| 18 |
Incorrect |
58 ms |
55120 KB |
Output isn't correct |
| 19 |
Incorrect |
57 ms |
51556 KB |
Output isn't correct |
| 20 |
Incorrect |
51 ms |
47440 KB |
Output isn't correct |
| 21 |
Incorrect |
132 ms |
127828 KB |
Output isn't correct |
| 22 |
Incorrect |
163 ms |
123476 KB |
Output isn't correct |
| 23 |
Incorrect |
126 ms |
106352 KB |
Output isn't correct |
| 24 |
Incorrect |
126 ms |
124752 KB |
Output isn't correct |
| 25 |
Incorrect |
234 ms |
219728 KB |
Output isn't correct |
| 26 |
Correct |
311 ms |
218532 KB |
Output is correct |
| 27 |
Incorrect |
228 ms |
219732 KB |
Output isn't correct |
| 28 |
Incorrect |
236 ms |
219476 KB |
Output isn't correct |
| 29 |
Incorrect |
282 ms |
219472 KB |
Output isn't correct |
| 30 |
Incorrect |
223 ms |
214868 KB |
Output isn't correct |
| 31 |
Incorrect |
145 ms |
140628 KB |
Output isn't correct |
| 32 |
Incorrect |
227 ms |
219504 KB |
Output isn't correct |
