Submission #42044772

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
INF = pow(10,10)
N,M = map(int, input().split())
S_list = list()
for i in range(N):
    S = list(input())
    S_list.append(S)
# Sを頂点と辺の形式に直す
edge = [set() for _ in range(N+1)]
inv_edge = [set() for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        if S_list[i][j] == "1":
            edge[i+1].add(i+1+j+1)      # SもS_listも0始まりなので頂点番号に直すためにi,jともに+1する
            inv_edge[i+1+j+1].add(i+1)
# dpで1からの最短距離を求める
dist_from_1 = [INF for _ in range(N+1)]
dist_from_1[1] = 0
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

INF = pow(10,10)

N,M = map(int, input().split())
S_list = list()
for i in range(N):
    S = list(input())
    S_list.append(S)

# Sを頂点と辺の形式に直す
edge = [set() for _ in range(N+1)]
inv_edge = [set() for _ in range(N+1)]

for i in range(N):
    for j in range(M):
        if S_list[i][j] == "1":
            edge[i+1].add(i+1+j+1)      # SもS_listも0始まりなので頂点番号に直すためにi,jともに+1する
            inv_edge[i+1+j+1].add(i+1)

# dpで1からの最短距離を求める
dist_from_1 = [INF for _ in range(N+1)]
dist_from_1[1] = 0

for i in range(1,N+1):
    for j in edge[i]:
        dist_from_1[j] = min(dist_from_1[j],dist_from_1[i]+1)

# dpでNへの最短距離を求める
dist_to_N = [INF for _ in range(N+1)]
dist_to_N[N] = 0

for i in range(N,0,-1):
    for j in inv_edge[i]:
        dist_to_N[j] = min(dist_to_N[j],dist_to_N[i]+1)

# 各kに対して通らないときの移動回数を求める
ans = list()
for k in range(2,N):
    part_ans = INF
    for u in range(k+1,min(k+M,N+1)):
        # k+1～k+M-1の都市に対して、(都市はNまでなのでmin条件を入れる)
        for v in inv_edge[u]:
            # 張られている辺を各々確認する
            if v < k:
                # もし辺の元がk以下ならkを通らないルートなので回数を算出
                dist = dist_from_1[v] + 1 + dist_to_N[u]
                part_ans = min(part_ans,dist)

    if part_ans != INF:
        ans.append(part_ans)
    else:
        ans.append(-1)

# 回答出力
print(*ans)

Submission Info

Judge Result