Submission #25497

#	Time	Username	Problem	Language	Result	Execution time	Memory
25497		admin	Young Zebra (KRIII5_YZ)	Pypy 2	7 / 7	406 ms	31 KiB

YZ

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)])

• Subtask 1: 7 / 7