作問アイディア - Githubissues

凹凸多角形

H 行 W 列のマス目があります。このマス目の、上から i 番目、左から j 番目のマスを、マス (i,j) と呼ぶことにします。各マスは黒または白に塗られています。S i,jが "#" ならばマス (i,j) は黒に塗られており、 "." ならば白に塗られています。ここで、黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、以下のことが保証されます。

黒に塗られたマスが少なくとも一つ存在する
黒に塗られた任意の 2 マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である

多角形の頂点がN個与えられるので、Sを復元してください。頂点は、H 行 W 列のマス目の格子点が与えられる。

H W N
row_1 col_1
row_2 col_2
...
row_i col_i
...
row_N col_N

制約 1≤H, W≤1000 4≤N≤1000 1≤row_i≤H+1 1≤col_i≤W+1

testcase1

- in ``` 4 4 12 2 2 2 3 3 1 3 2 3 3 3 4 4 1 4 4 4 2 4 3 5 2 5 3 ``` - out ``` . . . . . # . . # # # . . # . . ```

testcase2

- in ``` 4 4 4 1 1 1 5 5 1 5 5 ``` - out ``` # # # # # # # # # # # # # # # # ```

testcase3

- in ``` 4 4 8 2 2 2 3 2 4 2 5 3 3 3 4 4 2 4 5 ``` - out ``` . . . . . . . . . # . # . # # # . . . . ```

ACコード案

```py from collections import deque H,W,N=map(int,input().split()) rows=[[] for _ in range(H+1)] cols=[[] for _ in range(W+1)] for _ in range(N): r,c=map(int,input().split()) r-=1 c-=1 rows[r].append(c) cols[c].append(r) h=[[False for _ in range(W)] for _ in range(H+1)] v=[[False for _ in range(W+1)] for _ in range(H)] for r in range(H+1): rows[r].sort() i=0 while i

参考：https://atcoder.jp/contests/abc191/tasks/abc191_c?lang=ja

tipstar0125 / atcoder

作問アイディア #52