#include <bits/stdc++.h>
#define int int64_t
using namespace std;
void setIO() {
cin.tie(0)->sync_with_stdio(0);
}
bool inside(int x, int y, int n, int m, vector<string> &grid) {
return (x > -1 && x < n && y > -1 && y < m && grid[x][y] != '.');
}
void solve() {
//cout << "zco";
int n, m;
cin >> n >> m;
vector<string> grid(n);
for(auto &x : grid) cin >> x;
deque<pair<int, int>> dq;
dq.push_back({0, 0});
vector<vector<int>> depth(n, vector<int>(n, 1e18));
depth[0][0] = 0;
vector<int> di { -1, 0, 1, 0} , dj { 0, 1, 0, -1};
//auto inside = [](int x, int y, int &n, int &m) { return (x > -1 && x < n && y > -1 && y < m); };
int ans = 1;
while(!dq.empty()) {
auto u = dq.front();
dq.pop_front();
ans = max(ans, depth[u.first][u.second]);
for(int i = 0; i < 4; i++) {
int x = u.first+di[i], y = u.second+dj[i];
if(inside(x, y, n, m, grid) && (depth[x][y] + (grid[x][y] != grid[u.first][u.second])) < depth[x][y]) {
depth[x][y] = depth[u.first][u.second] + (grid[u.first][u.second] != grid[x][y]);
if(grid[u.first][u.second] != grid[x][y]) dq.push_back({x, y});
else dq.push_front({x, y});
}
}
}
cout << ans+1;
}
int32_t main() {
setIO();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2652 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 |
1 ms |
2512 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
348 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 |
860 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 14 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
2908 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 17 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 18 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
114700 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
15708 KB |
Output isn't correct |
| 3 |
Incorrect |
70 ms |
159148 KB |
Output isn't correct |
| 4 |
Incorrect |
17 ms |
35924 KB |
Output isn't correct |
| 5 |
Incorrect |
44 ms |
89584 KB |
Output isn't correct |
| 6 |
Incorrect |
74 ms |
159060 KB |
Output isn't correct |
| 7 |
Incorrect |
44 ms |
125780 KB |
Output isn't correct |
| 8 |
Incorrect |
41 ms |
114768 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 11 |
Incorrect |
43 ms |
121172 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 13 |
Incorrect |
7 ms |
15748 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
8796 KB |
Output isn't correct |
| 15 |
Incorrect |
6 ms |
10332 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
2908 KB |
Output isn't correct |
| 17 |
Incorrect |
18 ms |
40532 KB |
Output isn't correct |
| 18 |
Incorrect |
20 ms |
40020 KB |
Output isn't correct |
| 19 |
Incorrect |
18 ms |
35780 KB |
Output isn't correct |
| 20 |
Incorrect |
14 ms |
31636 KB |
Output isn't correct |
| 21 |
Incorrect |
41 ms |
95020 KB |
Output isn't correct |
| 22 |
Incorrect |
37 ms |
89444 KB |
Output isn't correct |
| 23 |
Incorrect |
31 ms |
65360 KB |
Output isn't correct |
| 24 |
Incorrect |
40 ms |
95288 KB |
Output isn't correct |
| 25 |
Incorrect |
72 ms |
159096 KB |
Output isn't correct |
| 26 |
Incorrect |
51 ms |
121920 KB |
Output isn't correct |
| 27 |
Incorrect |
71 ms |
159056 KB |
Output isn't correct |
| 28 |
Incorrect |
71 ms |
159268 KB |
Output isn't correct |
| 29 |
Incorrect |
80 ms |
159056 KB |
Output isn't correct |
| 30 |
Incorrect |
68 ms |
153440 KB |
Output isn't correct |
| 31 |
Incorrect |
42 ms |
101912 KB |
Output isn't correct |
| 32 |
Incorrect |
69 ms |
159240 KB |
Output isn't correct |
