JOI2012予選E イルミネーション

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

幅優先探索

はじめに

カテゴリー競プロ初中級者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
    36
    import 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日