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']))
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 |
353 ms |
30 KB |
Output is correct |
| 2 |
Correct |
290 ms |
30 KB |
Output is correct |
| 3 |
Correct |
306 ms |
30 KB |
Output is correct |
| 4 |
Correct |
320 ms |
30 KB |
Output is correct |
| 5 |
Correct |
331 ms |
30 KB |
Output is correct |
| 6 |
Correct |
266 ms |
30 KB |
Output is correct |
| 7 |
Correct |
329 ms |
30 KB |
Output is correct |
| 8 |
Correct |
294 ms |
30 KB |
Output is correct |
| 9 |
Correct |
383 ms |
30 KB |
Output is correct |
| 10 |
Correct |
257 ms |
30 KB |
Output is correct |
| 11 |
Correct |
279 ms |
31 KB |
Output is correct |
| 12 |
Correct |
297 ms |
31 KB |
Output is correct |
| 13 |
Correct |
337 ms |
31 KB |
Output is correct |
| 14 |
Correct |
311 ms |
31 KB |
Output is correct |
| 15 |
Correct |
406 ms |
31 KB |
Output is correct |
| 16 |
Correct |
310 ms |
31 KB |
Output is correct |
| 17 |
Correct |
251 ms |
31 KB |
Output is correct |
| 18 |
Correct |
218 ms |
31 KB |
Output is correct |
| 19 |
Correct |
220 ms |
31 KB |
Output is correct |
| 20 |
Correct |
302 ms |
31 KB |
Output is correct |
| 21 |
Correct |
308 ms |
31 KB |
Output is correct |
| 22 |
Correct |
323 ms |
31 KB |
Output is correct |
| 23 |
Correct |
318 ms |
31 KB |
Output is correct |
| 24 |
Correct |
357 ms |
31 KB |
Output is correct |
| 25 |
Correct |
393 ms |
31 KB |
Output is correct |
| 26 |
Correct |
25 ms |
31 KB |
Output is correct |
| 27 |
Correct |
26 ms |
31 KB |
Output is correct |
| 28 |
Correct |
72 ms |
31 KB |
Output is correct |
| 29 |
Correct |
95 ms |
31 KB |
Output is correct |
| 30 |
Correct |
32 ms |
31 KB |
Output is correct |
| 31 |
Correct |
31 ms |
31 KB |
Output is correct |
| 32 |
Correct |
63 ms |
31 KB |
Output is correct |
| 33 |
Correct |
46 ms |
31 KB |
Output is correct |
| 34 |
Correct |
30 ms |
31 KB |
Output is correct |
| 35 |
Correct |
38 ms |
31 KB |
Output is correct |
| 36 |
Correct |
76 ms |
31 KB |
Output is correct |
| 37 |
Correct |
131 ms |
31 KB |
Output is correct |
| 38 |
Correct |
93 ms |
31 KB |
Output is correct |
| 39 |
Correct |
121 ms |
31 KB |
Output is correct |
| 40 |
Correct |
103 ms |
31 KB |
Output is correct |
