競プロ初中級者100問

ABC088D Grid Repainting

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

深さ優先探索

はじめに

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

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

問題

https://atcoder.jp/contests/abc088/tasks/abc088_d

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

幅優先探索はキューによって実装できます。

Pythonの場合、キューはqueue.Queueやcollections.dequeを利用すると良いでしょう。いずれも標準ライブラリです。

この記事ではqueue.Queueを用います。

この問題を解くまえに

この問題は幅優先探索の応用です。まずは、ABC007C 幅優先探索を先に解いても良いでしょう。

方針

  • ゴールにたどり着くまでに通ったマス以外の白マスは黒く塗りつぶすことができる。
    • つまり出来るだけ少ないマスを通ってゴールにたどり着けば良いので、最短経路問題に帰着される。
      • ここでは幅優先探索を用いて最短経路問題を解く

幅優先探索の実装

  • キューを作成する。キューの各要素は（y座標、z座標、スタート地点からの距離）として利用していく。
  • キューにスタート地点をenqueueする。
  • 幅優先探索を行う。具体的には、以下の処理をキューが空になるまで繰り返す。
    • dequeueする
    • 訪問済みの場合は無視する
    • 未訪問の場合
      • 訪問フラグを立てる
      • 移動可能かを確認し、enqueueする

ポイント

訪問済みかどうかの確認はenqueueする前には必須である。

この問題の場合、dequeueした後には必須ではないが確認するべきだと思われる。
（スタート地点からの距離が等しいマスが、同じマスを複数回enqueueする可能性があり、queueのサイズが肥大化するためTLEやMLEのリスクが増える）

コード

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
import sys
import queue
input = sys.stdin.readline
sys.setrecursionlimit(int(1E+7))
dxdy = ((-1,0), (1,0), (0,-1), (0,1))
H, W = map(int,input().split())
maze = []
visited = [ [0]*W for _ in range(H)]
black = 0
for h in range(H):
    s = input()
    maze.append(s)
    for c in s:
        if c=='#':
            black += 1
q = queue.Queue()
q.put((0,0,0))
cost = -1
while(not q.empty()):
    y, x, d = q.get()
    if x == W-1 and y == H-1:
        cost = d
        break
    if visited[y][x] == 1:
        continue
    else:
        visited[y][x] = 1
        for dx, dy in  dxdy:
            if (0<= x+dx < W) and (0<= y+dy < H):                
                if visited[y+dy][x+dx] == 0 and maze[y+dy][x+dx]=='.':
                    q.put((y+dy,x+dx,d+1))
if cost==-1:
    print (-1)
else:
    print (H*W-cost-1-black)

記事情報

  • 投稿日：2020年4月17日
  • 最終更新日：2020年5月8日