競プロ初中級者100問

JOI2011予選E チーズ

この記事で使うアルゴリズム

幅優先探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e

この問題は幅優先探索で解くことができます。

方針

工場から次の工場への距離を幅優先探索で最小コストを計算する操作を繰り返せば良いです。計算量はO(NHW)となります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利
H, W, N = map(int,input().split())

maze = []

for h in range(H):
    s = input()
    maze.append(s) # 二次元リストにせず、文字列のリストのままでOK


def solve(sx ,sy, goal):
    dist = [ [-1]*W for _ in range(H)]
    dist[sy][sx] = 0
    q = deque()
    q.append((sy,sx)) # スタート地点をenqueue
    while(q):
        y, x = q.popleft()
        if maze[y][x] == goal: # ゴールにたどり着いたら終了
            break
        else:
            for dx, dy in  dxdy:
                if (0<= x+dx < W) and (0<= y+dy < H) and dist[y+dy][x+dx] == -1 and maze[y+dy][x+dx]!='X': # 見訪問かつ通行可能か
                    q.append((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x] + 1 # 距離を記録
    return x,y,dist[y][x]

for i in range(H):
    for j in range(W):
        if maze[i][j]=='S':
            sx = j
            sy = i
ans = 0
for n in range(1,N+1):
    sx, sy, d = solve(sx, sy, str(n))
    ans += d
print (ans)

記事情報

  • 投稿日：2020年5月30日
  • 最終更新日：2020年5月30日