引用
（引用）
問題文
H 行 W 列のマス目があります。このマス目の、上から i 番目、左から j 番目のマスを、マス(i,,j)と呼ぶことにします。
各マスは黒または白に塗られています。Si,jが#ならばマス (i,,j)は黒に塗られており、.ならば白に塗られています。
マス目の一番外側のマス、すなわち (1,j),(H,j),(i,1),(i,W)のいずれかの形で表されるマスは白に塗られていることが保証されます。
黒に塗られた部分を多角形として見たとき、これが (最小で) 何角形になるかを求めてください。
ここで、黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、以下のことが保証されます。
・黒に塗られたマスが少なくとも一つ存在する
・黒に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である
・白に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)
制約
3≤H≤10
3≤W≤10
Si,jは#または.
S1,jおよびSH,jは.
Si,1およびSi,Wは.
黒に塗られた部分は一つの自己交叉のない多角形となる
AtCoder Beginner Contest 191 C – Digital Graffitiより引用
入力
入力は以下の形式で標準入力から与えられる。
H W S1,1S1,2S1,3…S1,W S2,1S2,2S2,3…S2,W S3,1S3,2S3,3…S3,W ⋮ SH,1SH,2SH,3…SH,W
出力
黒に塗られた部分を n 角形として見ることができるような最小の n を出力せよ。
入力例 1
5 5 ..... .###. .###. .###. .....
出力例 2
4
マス目の左上、左下、右上、右下の隅をそれぞれ (0,0),(H,0),(0,W),(H,W) とする座標系で表すと、与えられる図形は (1,1),(4,1),(4,4),(1,4) を頂点とする 4 角形です。
考えてみました
正直にぜんぜんわからんかったのと、文面の意味もわからなかったので、解説を読んで理解。
マス目をS(i,j)・・・として考える
格子点を(h,w)・・・として考える
そして、自己交叉のない多角形という事で下の８パターンのうち、⑦と⑧だけが多角形の頂点になるはず。大外の一周は『白』確定なので、(1,1)〜(H-1,W-1)で周りが⑦or⑧になっている格子点をカウントする。
forで１〜H-1、１〜W-1で二重に回して、下図の(h,w)ごとに周りが’#’が１or３をカウント
H, W = map(int,input().split())
A = []
for a in range(H):
A.append(list(input()))
count = 0
for h in range(1,H):
for w in range(1, W):
if [A[h-1][w-1], A[h-1][w], A[h][w-1], A[h][w]].count('#')==1 or [A[h-1][w-1], A[h-1][w], A[h][w-1], A[h][w]].count('#')==3:
count += 1
print(count)やり方わかったら、意外とあっさりいけました
コメント