AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度6 イルミネーション

問題原文

atcoder.jp

問題要旨

あまりにもめんどうなので書きません()

解法

くそくそくそくそくそくそめんどくさ実装!!!!!w
方針を間違えると大事故を起こしそう。

方針としては、

  1. 1 の6方向について、(6 - 1の数)分外周に必要とする
  2. ここから、外からたどり着けない内の 0 を囲っている部分を引く必要がある
  3. 2を満たすようなものは、盤面の外からたどり着けないようなもの
  4. よって便宜上盤面の外側を x とかで定義してあげて、dfs等で探索する
  5. 外からたどり着けない内の 0 を囲っている部分について、隣接している 1 の数だけ余計にカウントしてしまっているので引く

という感じ

実装

h の偶奇で移動成分が変わるので注意!(問題文ちゃんと読もう)

W, H = map(int, input().split())
G = [list(input().split()) for _ in range(H)]

# 外周を囲む
for h in range(H):
    G[h] = ['x'] + G[h] + ['x']
G.insert(0, ['x'] * (W + 2))
G.append(['x'] * (W + 2))
W, H = len(G[0]), len(G)


directions_list = [
    [(0, 1), (0, -1), (-1, 0), (1, 0), (1, -1), (-1, -1)],
    [(0, 1), (0, -1), (-1, 1), (1, 1), (1, 0), (-1, 0)]
]
visited = [[0] * W for _ in range(H)]
stack = [(0, 0), (1, 0)]
while stack:
    h, w = stack.pop()
    visited[h][w] = 1
    directions = directions_list[h % 2]

    for dh, dw in directions:
        fh, fw = h + dh, w + dw
        if not ((0 <= fh < H) and (0 <= fw < W)):
            continue

        if visited[fh][fw]:
            continue

        if G[fh][fw] == '1':
            continue

        G[fh][fw] = 'x'
        stack.append((fh, fw))


ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == 'x':
            continue

        directions = directions_list[h % 2]
        if G[h][w] == '1':
            cnt = 0
            for dh, dw in directions:
                fh, fw = h + dh, w + dw
                if not ((0 <= fh < H) and (0 <= fw < W)):
                    continue

                if G[fh][fw] == '1':
                    cnt += 1

            ans += 6 - cnt

        if G[h][w] == '0':
            cnt = 0
            for dh, dw in directions:
                fh, fw = h + dh, w + dw
                if not ((0 <= fh < H) and (0 <= fw < W)):
                    continue

                if G[fh][fw] == '1':
                    cnt += 1

            ans -= cnt

print(ans)

感想

一発ACでした(にっこり)