Submission #63061322

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque, defaultdict
N = int(input())
C = [input() for _ in range(N)]
tree = [[] for _ in range(N)]
rtree = [[] for _ in range(N)]
group_t = [defaultdict(list) for _ in range(N)]
group_r = [defaultdict(list) for _ in range(N)]
for i in range(N):
    for j in range(N):
        nm = C[i][j]
        if nm != '-':
            tree[i].append((j,nm))
            rtree[j].append((i,nm))
            group_t[i][nm].append(j)
            group_r[j][nm].append(i)
    
INF = 4*N
dp = [[INF]*N for _ in range(N)]
Q = deque()
for i in range(N):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque, defaultdict
N = int(input())
C = [input() for _ in range(N)]
tree = [[] for _ in range(N)]
rtree = [[] for _ in range(N)]
group_t = [defaultdict(list) for _ in range(N)]
group_r = [defaultdict(list) for _ in range(N)]

for i in range(N):
    for j in range(N):
        nm = C[i][j]
        if nm != '-':
            tree[i].append((j,nm))
            rtree[j].append((i,nm))
            group_t[i][nm].append(j)
            group_r[j][nm].append(i)
    
INF = 4*N
dp = [[INF]*N for _ in range(N)]
Q = deque()
for i in range(N):
    dp[i][i] = 0
    Q.append((i, i))
for i in range(N):
    for j,nm in tree[i]:
        if dp[i][j] > 1:
            dp[i][j] = 1
            Q.append((i,j))
    
while Q:
    i,j = Q.popleft()
    d = dp[i][j]
    for c in group_r[i]:
        if c in group_t[j]:
            for p in group_r[i][c]:
                for q in group_t[j][c]:
                    nd = d+2
                    if nd < dp[p][q]:
                        dp[p][q] = nd
                        Q.append((p,q))
    

for s in range(N):
    ans = []
    for t in range(N):
        ans.append(dp[s][t] if dp[s][t] != INF else -1)
    print(*ans)

Submission Info

Judge Result