Problem:


イルミネーション (Illumination)  

  問題

JOI 社の建物は図のような 1 辺 1 メートルの正六角形をつなぎ合わせた形である．クリスマスが近づいているので，JOI 社では建物の壁面をイルミネーションで飾り付けることにした．ただし，外から見えない部分にイルミネーションを施すのは無駄なので，イルミネーションは外から建物の中を通らずに行くことのできる壁面にのみ飾り付けることにした．

図: JOI 社の建物の配置の例

上の図は上空から見た JOI 社の建物の配置の例である．正六角形内の数字は座標を表す．灰色の正六角形は建物がある場所を表し，白色の正六角形は建物がない場所を表す．この例では，赤の実線で示される部分がイルミネーションで飾り付けを行う壁面となり，その壁面の長さの合計は 64 メートルとなる．

JOI 社の建物の配置を表す地図が与えられたとき，飾り付けを行う壁面の長さの合計を求めるプログラムを作成せよ．ただし，地図の外側は自由に行き来できるものとし，隣接した建物の間は通ることはできないものとする．

  入力

入力ファイルの 1 行目には 2 つの整数 W, H (1 ≦ W ≦ 100，1 ≦ H ≦ 100) が空白を区切りとして書かれている．続く H 行には JOI 社の建物の配置が書かれている．i + 1 行目 (1 ≦ i ≦ H) には W 個の整数が空白を区切りとして書かれており，j 個目 (1 ≦ j ≦ W) の整数は座標 (j, i) の正六角形に建物がある時は 1 であり，ない時は 0 である．また，与えられる入力データには建物が必ず 1 つ以上ある．

地図は以下の規則によって記述されている．

地図の最も北の行の最も西の正六角形は座標 (1, 1) である．

座標 (x, y) の正六角形に隣接する東隣の正六角形は座標 (x + 1, y) である．

y が奇数の時，座標 (x, y) の正六角形に隣接する南西の正六角形の座標は (x, y + 1) である．

y が偶数の時，座標 (x, y) の正六角形に隣接する南東の正六角形の座標は (x, y + 1) である．

  出力

イルミネーションで飾り付けを行う壁面の長さの合計を 1 行で出力せよ．

  入出力例

入力例 1

  

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

出力例 1

   

64

入出力例 1 は問題文中の例に対応しており，イルミネーションで飾り付けを行う壁面の長さの合計は 64 メートルである．

入力例 2

  

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

出力例 2

56

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0


Sample output:
64

Submission status: Wrong Answer

Solution code:
def solve():
    from collections import deque
    from copy import deepcopy
    W, H = map(int, input().split())
    a = [[0]*(W+2)] + [list(map(int, ("0 "+input()+" 0").split())) for _ in [0]*H] + [[0]*(W+2)]
    result = 0

    visited = deepcopy(a)
    dq = deque([(0, 0)])
    append, popleft = dq.append, dq.popleft

    while dq:
        x, y = popleft()
        neighbour = [(-1, 0), (1, 0)] + ([(-1, -1), (0, -1), (-1, 1), (0, 1)] if y%2 == 0 else [(0, -1), (1, -1), (0, 1), (1, 1)])
        for dx, dy in neighbour:
            nx, ny = dx+x, dy+y
            if 0 <= nx < W+2 and 0 <= ny < H+2:
                result += a[ny][nx]

        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < W+2 and 0 <= ny < H+2 and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                append((nx, ny))

    print(result)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
W, H = map(int, input().split())
m = [list(map(int, input().split())) for i in range(H)]
dx = [[1, 1, 1, 0, -1, 0], [0, 1, 0, -1, -1, -1]]
dy = [-1, 0, 1, 1, 0, -1]
def dfs(x, y):
    if m[y][x] != 0:
        return
    m[y][x] = 2
    for xx, yy in zip(dx[y % 2], dy):
        tx, ty = x + xx, y + yy
        if 0 <= tx < W and 0 <= ty < H:
            dfs(tx, ty)

for x in range(W):
    dfs(x, 0)
    dfs(x, H - 1)
for y in range(H):
    dfs(0, y)
    dfs(W - 1, y)

from itertools import product
n = 0
for x, y in product(range(W), range(H)):
    if m[y][x] != 1:
        continue
    fn = n
    for xx, yy in zip(dx[y % 2], dy):
        tx, ty = x + xx, y + yy
        if 0 <= tx < W and 0 <= ty < H:
            if m[ty][tx] == 2:
                n += 1
        else:
            n += 1
print(n)

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    from copy import deepcopy
    W, H = map(int, input().split())
    a = [[0]*(W+2)] + [list(map(int, ("0 "+input()+" 0").split())) for _ in [0]*H] + [[0]*(W+2)]
    result = 0

    visited = deepcopy(a)
    dq = deque([(0, 0)])
    append, popleft = dq.append, dq.popleft

    while dq:
        x, y = popleft()
        neighbour = [(-1, 0), (1, 0)] + ([(-1, -1), (0, -1), (-1, 1), (0, 1)] if y%2 == 0 else [(0, -1), (1, -1), (0, 1), (1, 1)])
        for dx, dy in neighbour:
            nx, ny = dx+x, dy+y
            if 0 <= nx < W+2 and 0 <= ny < H+2:
                result += a[ny][nx]

        for dx, dy in neighbour:
            nx, ny = x+dx, y+dy
            if 0 <= nx < W+2 and 0 <= ny < H+2 and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                append((nx, ny))

    print(result)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

WALL = 100
w, h = map(int,input().split())
lst = [[WALL] + list(map(int,input().split())) + [WALL] for i in range(h)]
lst.insert(0, [WALL] * (w + 2))
lst.append([WALL] * (w + 2))

visited = [[0] * (w + 2) for _ in range(h + 2)]
hold = []

def search(x, y):

  if lst[x][y] == WALL:
    visited[x][y] = 3
    return 3

  if lst[x][y] == 1:
    visited[x][y] = 2
    return 2

  visited[x][y] = 1
  hold.append((x, y))

  if not x % 2:
    pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
  else:
    pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
  
  ret = 0
  for t in pairs:
    tx, ty = t[0], t[1]
    a = 0
    if not visited[tx][ty]:
      a = search(tx, ty)
    elif visited[tx][ty] == 3:
      a = 3
    elif visited[tx][ty] == 2:
      a = 2
    if a > ret:
      ret = a

  return ret

for x in range(1, h + 1):
  for y in range(1, w + 1):
    if not visited[x][y] and not lst[x][y]:
      stat = search(x, y)
      for point in hold:
        visited[point[0]][point[1]] = stat
      hold.clear()

ans = 0
for x in range(1, h + 1):
  for y in range(1, w + 1):
    if lst[x][y]:
      if not x % 2:
        pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
      else:
        pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
      for t in pairs:
        tx, ty = t[0], t[1]
        if (visited[tx][ty] in [0,3]) and (lst[tx][ty] in [WALL, 0]):
          ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

WALL = 100
w, h = map(int,input().split())
lst = [[WALL] + list(map(int,input().split())) + [WALL] for i in range(h)]
lst.insert(0, [WALL] * (w + 2))
lst.append([WALL] * (w + 2))

visited = [[0] * (w + 2) for _ in range(h + 2)]
hold = []
app = hold.append

def search(x, y):

  if lst[x][y] == WALL:
    visited[x][y] = 3
    return 3

  if lst[x][y] == 1:
    visited[x][y] = 2
    return 2

  visited[x][y] = 1
  app((x, y))

  if not x % 2:
    pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
  else:
    pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
  
  ret = 0
  for t in pairs:
    tx, ty = t[0], t[1]
    v = visited[tx][ty]
    a = 0
    if not v:
      a = search(tx, ty)
    elif v == 3:
      a = 3
    elif v == 2:
      a = 2
    if a > ret:
      ret = a
  return ret

def main():

  for x in range(1, h + 1):
    for y in range(1, w + 1):
      if not visited[x][y] and not lst[x][y]:
        stat = search(x, y)
        for point in hold:
          visited[point[0]][point[1]] = stat
        hold.clear()
  
  ans = 0
  for x in range(1, h + 1):
    for y in range(1, w + 1):
      if lst[x][y]:
        if not x % 2:
          pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
        else:
          pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
        for t in pairs:
          tx, ty = t[0], t[1]
          if (visited[tx][ty] in [0,3]) and (lst[tx][ty] in [WALL, 0]):
            ans += 1
  
  print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Illumination
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569

"""
import sys


def solve(data, w, h):
    invisible_area = set()
    visible_area = set()
    visited = set()
    for y in range(h):
        for x in range(w):
            visited.add((x, y))
            if data[y][x] == 1:
                invisible_area.add((x, y))
            is_visible = False
            if (x, y) in invisible_area or (x, y) in visible_area:
                continue
            area = {(x, y)}
            stack = [(x, y)]
            while stack:
                cx, cy = stack.pop()
                visited.add((cx, cy))
                dxy = ((cx, cy-1), (cx+1, cy-1), (cx-1, cy), (cx+1, cy), (cx, cy+1), (cx+1, cy+1)) if cy % 2 == 0 else \
                      ((cx-1, cy-1), (cx, cy-1), (cx-1, cy), (cx+1, cy), (cx-1, cy+1), (cx, cy+1))
                for nx, ny in dxy:
                    if not (0 <= nx < w) or not (0 <= ny < h):
                        is_visible = True
                    if 0 <= nx < w and 0 <= ny < h and data[ny][nx] == 0 and (nx, ny) not in visited:
                        stack.append((nx, ny))
                        area.add((nx, ny))
            if is_visible:
                visible_area |= area
            else:
                invisible_area |= area

    ans = 0
    for cy in range(h):
        for cx in range(w):
            if data[cy][cx] == 1:
                dxy = ((cx, cy-1), (cx+1, cy-1), (cx-1, cy), (cx+1, cy), (cx, cy+1), (cx+1, cy+1)) if cy % 2 == 0 else \
                ((cx-1, cy-1), (cx, cy-1), (cx-1, cy), (cx+1, cy), (cx-1, cy+1), (cx, cy+1))
                ans += 6 - sum((nx, ny) in invisible_area for nx, ny in dxy)
    return ans



def main(args):
    w, h = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(h)]
    ans = solve(data, w, h)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
W, H = map(int, input().split())
m = [list(map(int, input().split())) for i in range(H)]
dx = [[1, 1, 1, 0, -1, 0], [0, 1, 0, -1, -1, -1]]
dy = [-1, 0, 1, 1, 0, -1]
def dfs(x, y):
    if m[y][x] != 0:
        return
    m[y][x] = 2
    for xx, yy in zip(dx[y % 2], dy):
        tx, ty = x + xx, y + yy
        if 0 <= tx < W and 0 <= ty < H:
            dfs(tx, ty)

for x in range(W):
    dfs(x, 0)
    dfs(x, H - 1)
for y in range(H):
    dfs(0, y)
    dfs(W - 1, y)

from itertools import product
n = 0
for x, y in product(range(W), range(H)):
    if m[y][x] != 1:
        continue
    fn = n
    for xx, yy in zip(dx[y % 2], dy):
        tx, ty = x + xx, y + yy
        if 0 <= tx < W and 0 <= ty < H:
            if m[ty][tx] == 2:
                n += 1
        else:
            n += 1
print(n)

Submission status: Runtime Error

Solution code:
WALL = 100
w, h = map(int,input().split())
lst = [[WALL] + list(map(int,input().split())) + [WALL] for i in range(h)]
lst.insert(0, [WALL] * (w + 2))
lst.append([WALL] * (w + 2))

visited = [[0] * (w + 2) for _ in range(h + 2)]
hold = []

def search(x, y):

  if lst[x][y] == WALL:
    visited[x][y] = 3
    return 3

  if lst[x][y] == 1:
    visited[x][y] = 2
    return 2

  visited[x][y] = 1
  hold.append((x, y))

  if not x % 2:
    pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
  else:
    pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
  
  ret = 0
  for t in pairs:
    tx, ty = t[0], t[1]
    a = 0
    if not visited[tx][ty]:
      a = search(tx, ty)
    elif visited[x][y] == 3:
      a = 3
    elif visited[x][y] == 2:
      a = 2
    if a > ret:
      ret = a

  return ret

for x in range(1, h + 1):
  for y in range(1, w + 1):
    if not visited[x][y] and not lst[x][y]:
      stat = search(x, y)
      for point in hold:
        visited[point[0]][point[1]] = stat
      hold.clear()

ans = 0
for x in range(1, h + 1):
  for y in range(1, w + 1):
    if lst[x][y]:
      if not x % 2:
        pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
      else:
        pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
      for t in pairs:
        tx, ty = t[0], t[1]
        if visited[tx][ty] in [0,3]:
          ans += 1

print(ans)