JOI難易度6 イルミネーション
問題原文
問題要旨
あまりにもめんどうなので書きません()
解法
くそくそくそくそくそくそめんどくさ実装!!!!!w
方針を間違えると大事故を起こしそう。
方針としては、
1
の6方向について、(6 -1
の数)分外周に必要とする- ここから、外からたどり着けない内の
0
を囲っている部分を引く必要がある - 2を満たすようなものは、盤面の外からたどり着けないようなもの
- よって便宜上盤面の外側を
x
とかで定義してあげて、dfs等で探索する - 外からたどり着けない内の
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でした(にっこり)