ABC191 C Digital Graffiti
まず, マス目を$ (H+1)×$ (W+1)個の点に帰着する. 与えられたマス目において$ (i,j)が#のとき, 頂点となるような候補は帰着した点において$ (i,j), (i+1, j), (i, j+1), (i+1, j+1)である.
それぞれの点について, その点をマスの周上に持つような4つのマスについて考える. 点が頂点となる必要十分条件は, その4つのマスのうち1つもしくは3つが#の場合である. これは手元で実験することによって導き出すことができる.
よってこれを順に調べていけばよい. 計算量は$ O(HW)となる.