この記事で使うアルゴリズム
幅優先探索
はじめに
カテゴリー競プロ初中級者100問では、Qiita
にて@e869120
さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPython
で解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e
この問題は幅優先探索を用いて解くことができます。
方針
- 周囲を1マス分だけ
0
でパディングします。建物がない箇所を幅優先探索し、建物にぶつかるたびにカウンタをインクリメントすることで、解を求めることができます。 - 六角形の配置となっておりやや扱いにくいですが、隣接するマスを工夫して扱うことで二次元配列として表現できます。
コード
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
36import sys
import queue
dxdy_odd = ((-1,0), (1,0), (0,-1), (0,1), (1,-1), (1,1)) # タプルやリストで持っておくと便利
dxdy_even = ((-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1)) # タプルやリストで持っておくと便利
W, H = map(int,input().split())
mp = []
mp.append([0]*(W+2))
for h in range(H):
s = list(map(int, input().split()))
mp.append([0]+s+[0])
mp.append([0]*(W+2))
visited = [ [0]*(W+2) for _ in range(H+2)]
ans = 0
q = queue.Queue()
q.put((0,0)) # (0,0)は建物がないので、スタート地点にする
while(not q.empty()):
y, x = q.get()
if visited[y][x] == 1: # 訪問済みの場合は無視する
continue
else:
visited[y][x] = 1 # 訪問フラグを立てる
if y%2 == 0:
dxdy = dxdy_even
else:
dxdy = dxdy_odd
for dx, dy in dxdy:
if (0<= x+dx < W+2) and (0<= y+dy < H+2): # 範囲内に収まっているか
if mp[y+dy][x+dx]==1:
ans += 1
else:
if visited[y+dy][x+dx]==0:
q.put((y+dy,x+dx))
print (ans)
記事情報
- 投稿日:2020年6月6日
- 最終更新日:2020年6月6日