Edit

【pythonでABC191を解説】C - Digital Graffiti

問題概要

問題ページ

C - Digital Graffiti
C - Digital Graffiti

問題ページへ移動する

問題文

\(H\) 行 \(W\) 列のマス目があります。このマス目の、上から \(i\) 番目、左から \(j\) 番目のマスを、マス \((i, j)\) と呼ぶことにします。
各マスは黒または白に塗られています。\(S_{i, j}\) が # ならばマス \((i, j)\) は黒に塗られており、. ならば白に塗られています。
マス目の一番外側のマス、すなわち \((1, j), (H, j), (i, 1), (i, W)\) のいずれかの形で表されるマスは白に塗られていることが保証されます。

黒に塗られた部分を多角形として見たとき、これが (最小で) 何角形になるかを求めてください。

ここで、黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、以下のことが保証されます。

  • 黒に塗られたマスが少なくとも一つ存在する
  • 黒に塗られた任意の \(2\) マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である
  • 白に塗られた任意の \(2\) マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)

制約

  • \(3 \le H \le 10\)
  • \(3 \le W \le 10\)
  • \(S_{i, j}\) は # または .
  • \(S_{1, j}, S_{H, j}\) は .
  • \(S_{i, 1}, S_{i, W}\) は .
  • 黒に塗られた部分は一つの自己交叉のない多角形となる

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [str(input().rstrip('\n')) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            t = 0
            for x, y in [[i, j], [i + 1, j], [i, j + 1], [i + 1, j + 1]]:
                if 0 <= x < h and 0 <= y < w:
                    t += 1 if s[x][y] == "#" else 0
            if t == 1 or t == 3:
                cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

-Edit
-