MOD = int(1e9 + 7)
import sys
sys.setrecursionlimit(10000000)
N, M = map(int, sys.stdin.readline().split())
S = ["" for _ in xrange(N)]
for i in xrange(N): S[i] = sys.stdin.readline().strip()
assert 1 <= N <= 400
assert 1 <= M <= 400
assert set(list("".join(S))).issubset(set(['B', 'W']))
assert all(len(line) == M for line in S)
visited = [[False for j in xrange(M)] for i in xrange(N)]
comp = [[0 for j in xrange(M)] for i in xrange(N)]
ans = [[-1 for j in xrange(M)] for i in xrange(N)]
pos = [[(0, 0) for j in xrange(M)] for i in xrange(N)]
num_components = 0
vertices = []
from collections import deque
def dfs (x, y, c):
que = deque([(x, y)])
que_len = 1
visited[x][y] = True
pos[x][y] = (x, y)
ret = 0
while que_len > 0:
rx, ry = que.popleft()
que_len -= 1
x = (rx + N * 2) % N
y = (ry + M * 2) % M
ret += 1
vertices.append((x, y))
for dx, dy in [(0, -1), (0, +1), (-1, 0), (+1, 0)]:
nx = (x + dx + N) % N
ny = (y + dy + M) % M
nrx = rx + dx
nry = ry + dy
if S[nx][ny] != c: continue
if not visited[nx][ny]:
visited[nx][ny] = True
pos[nx][ny] = (nrx, nry)
que.append((nrx, nry))
que_len += 1
elif pos[nx][ny] != (nrx, nry):
ret = 1e9
return ret
"""
if visited[x][y]: return 0
pos[x][y] = (rx, ry)
visited[x][y] = True
vertices.append((x, y))
#print(x, y, rx, ry, c)
ret = 1
return ret"""
for i in xrange(N):
for j in xrange(M):
if not visited[i][j]:
num_components += 1
vertices = []
sz = dfs(i, j, S[i][j])
#print(i, j, sz, vertices)
if sz < 1e9:
for x, y in vertices: ans[x][y] = sz
print "\n".join([" ".join(map(str, ans[i])) for i in xrange(N)])
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
303 ms |
35 KB |
Output is correct |
| 2 |
Correct |
275 ms |
35 KB |
Output is correct |
| 3 |
Correct |
274 ms |
35 KB |
Output is correct |
| 4 |
Correct |
310 ms |
35 KB |
Output is correct |
| 5 |
Correct |
299 ms |
35 KB |
Output is correct |
| 6 |
Correct |
281 ms |
35 KB |
Output is correct |
| 7 |
Correct |
333 ms |
35 KB |
Output is correct |
| 8 |
Correct |
245 ms |
35 KB |
Output is correct |
| 9 |
Correct |
405 ms |
36 KB |
Output is correct |
| 10 |
Correct |
266 ms |
36 KB |
Output is correct |
| 11 |
Correct |
307 ms |
37 KB |
Output is correct |
| 12 |
Correct |
296 ms |
37 KB |
Output is correct |
| 13 |
Correct |
305 ms |
37 KB |
Output is correct |
| 14 |
Correct |
297 ms |
37 KB |
Output is correct |
| 15 |
Correct |
365 ms |
37 KB |
Output is correct |
| 16 |
Correct |
293 ms |
37 KB |
Output is correct |
| 17 |
Correct |
254 ms |
37 KB |
Output is correct |
| 18 |
Correct |
262 ms |
37 KB |
Output is correct |
| 19 |
Correct |
203 ms |
37 KB |
Output is correct |
| 20 |
Correct |
340 ms |
37 KB |
Output is correct |
| 21 |
Correct |
305 ms |
37 KB |
Output is correct |
| 22 |
Correct |
314 ms |
37 KB |
Output is correct |
| 23 |
Correct |
327 ms |
37 KB |
Output is correct |
| 24 |
Correct |
327 ms |
37 KB |
Output is correct |
| 25 |
Correct |
388 ms |
37 KB |
Output is correct |
| 26 |
Correct |
29 ms |
37 KB |
Output is correct |
| 27 |
Correct |
28 ms |
37 KB |
Output is correct |
| 28 |
Correct |
64 ms |
37 KB |
Output is correct |
| 29 |
Correct |
54 ms |
37 KB |
Output is correct |
| 30 |
Correct |
30 ms |
37 KB |
Output is correct |
| 31 |
Correct |
28 ms |
37 KB |
Output is correct |
| 32 |
Correct |
52 ms |
37 KB |
Output is correct |
| 33 |
Correct |
42 ms |
37 KB |
Output is correct |
| 34 |
Correct |
28 ms |
37 KB |
Output is correct |
| 35 |
Correct |
31 ms |
37 KB |
Output is correct |
| 36 |
Correct |
91 ms |
37 KB |
Output is correct |
| 37 |
Correct |
109 ms |
37 KB |
Output is correct |
| 38 |
Correct |
88 ms |
37 KB |
Output is correct |
| 39 |
Correct |
102 ms |
37 KB |
Output is correct |
| 40 |
Correct |
79 ms |
37 KB |
Output is correct |
