Submission #22499

#	Time	Username	Problem	Language	Result	Execution time	Memory
22499		admin	Young Zebra (KRIII5_YZ)	Pypy 2	7 / 7	405 ms	37 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']))
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)])

• Subtask 1: 7 / 7