from collections import deque
m, n = map(int, input().strip().split())
grid = []
for _ in range(m):
grid.append(list(input().strip()))
q = deque([(0, 0)])
visited = set()
costs = [[float("inf")] * n for _ in range(m)]
costs[0][0] = 1
ans = 1
while q:
x, y = q.popleft()
ans = max(ans, costs[x][y])
visited.add((x, y))
for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
n_x, n_y = x + dx, y + dy
if 0 <= n_x < m and 0 <= n_y < n and grid[n_x][n_y] != "." and (n_x, n_y) not in visited:
loss = 0 if grid[n_x][n_y] == grid[x][y] else 1
if loss + costs[x][y] < costs[n_x][n_y]:
costs[n_x][n_y] = loss + costs[x][y]
q.append((n_x, n_y)) if loss == 1 else q.appendleft((n_x, n_y))
print(ans)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1397 ms |
37744 KB |
Output is correct |
| 2 |
Correct |
16 ms |
3256 KB |
Output is correct |
| 3 |
Correct |
24 ms |
3304 KB |
Output is correct |
| 4 |
Correct |
896 ms |
23112 KB |
Output is correct |
| 5 |
Correct |
119 ms |
8496 KB |
Output is correct |
| 6 |
Correct |
16 ms |
3248 KB |
Output is correct |
| 7 |
Correct |
23 ms |
3384 KB |
Output is correct |
| 8 |
Correct |
40 ms |
3740 KB |
Output is correct |
| 9 |
Correct |
23 ms |
3660 KB |
Output is correct |
| 10 |
Correct |
157 ms |
8120 KB |
Output is correct |
| 11 |
Correct |
235 ms |
8480 KB |
Output is correct |
| 12 |
Correct |
529 ms |
16548 KB |
Output is correct |
| 13 |
Correct |
118 ms |
8512 KB |
Output is correct |
| 14 |
Correct |
124 ms |
8532 KB |
Output is correct |
| 15 |
Correct |
1066 ms |
34784 KB |
Output is correct |
| 16 |
Correct |
1461 ms |
37612 KB |
Output is correct |
| 17 |
Correct |
596 ms |
21180 KB |
Output is correct |
| 18 |
Correct |
922 ms |
23084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
6940 KB |
Output is correct |
| 2 |
Execution timed out |
2011 ms |
92508 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2074 ms |
306156 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2094 ms |
130096 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2092 ms |
223844 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2050 ms |
308608 KB |
Time limit exceeded |
| 7 |
Correct |
82 ms |
6720 KB |
Output is correct |
| 8 |
Correct |
90 ms |
6940 KB |
Output is correct |
| 9 |
Correct |
177 ms |
8976 KB |
Output is correct |
| 10 |
Correct |
61 ms |
5300 KB |
Output is correct |
| 11 |
Correct |
62 ms |
6108 KB |
Output is correct |
| 12 |
Correct |
76 ms |
5184 KB |
Output is correct |
| 13 |
Execution timed out |
2061 ms |
92568 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2078 ms |
79352 KB |
Time limit exceeded |
| 15 |
Correct |
1473 ms |
69228 KB |
Output is correct |
| 16 |
Correct |
2000 ms |
72244 KB |
Output is correct |
| 17 |
Execution timed out |
2089 ms |
135300 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2086 ms |
146728 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2089 ms |
130208 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2078 ms |
132240 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2060 ms |
205600 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2080 ms |
223832 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2093 ms |
177932 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2053 ms |
217580 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2074 ms |
311188 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2068 ms |
254632 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2096 ms |
299916 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2101 ms |
308268 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2068 ms |
304152 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2095 ms |
296488 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2074 ms |
213624 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2060 ms |
295364 KB |
Time limit exceeded |
