#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, dist[N][N];
char s[N][N];
bool valid(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m && s[x][y] != '*';
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
}
deque<pair<int, int>> dq;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dist[i][j] = inf;
}
}
dist[1][1] = 1;
dq.emplace_back(1, 1);
while (!dq.empty()) {
pair<int, int> p = dq.front();
dq.pop_front();
int x = p.first;
int y = p.second;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (!valid(nx, ny)) {
continue;
}
int w = (s[x][y] != s[nx][ny] ? 1 : 0);
if (dist[nx][ny] > dist[x][y] + w) {
dist[nx][ny] = dist[x][y] + w;
if (w == 0) {
dq.emplace_front(nx, ny);
} else {
dq.emplace_back(nx, ny);
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (valid(i, j)) {
ans = max(ans, dist[i][j]);
}
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
zoo.cpp: In function 'int main()':
zoo.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
zoo.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%s", s[i] + 1);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
824 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
436 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
700 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
824 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
1 ms |
724 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
1 ms |
724 KB |
Output is correct |
15 |
Correct |
1 ms |
692 KB |
Output is correct |
16 |
Correct |
14 ms |
6100 KB |
Output is correct |
17 |
Correct |
11 ms |
6116 KB |
Output is correct |
18 |
Correct |
10 ms |
6124 KB |
Output is correct |
19 |
Correct |
11 ms |
6052 KB |
Output is correct |
20 |
Correct |
10 ms |
5972 KB |
Output is correct |
21 |
Correct |
45 ms |
5936 KB |
Output is correct |
22 |
Correct |
39 ms |
5916 KB |
Output is correct |
23 |
Correct |
41 ms |
5972 KB |
Output is correct |
24 |
Correct |
45 ms |
6228 KB |
Output is correct |
25 |
Correct |
42 ms |
6084 KB |
Output is correct |
26 |
Correct |
42 ms |
5960 KB |
Output is correct |
27 |
Correct |
41 ms |
5972 KB |
Output is correct |
28 |
Correct |
41 ms |
5972 KB |
Output is correct |
29 |
Correct |
41 ms |
6140 KB |
Output is correct |
30 |
Correct |
47 ms |
6100 KB |
Output is correct |