We can see that a point \((x, y)\) is a vertex if and only if there are exactly one or three #’s in the four cells surrounding the point \((S_{x, y}, S_{x + 1, y}, S_{x, y + 1}, S_{x + 1, y + 1})\).

Note:
If there are exactly \(2\) #’s around them, it is not possible that they are placed diagonally, since the shape does not have self-intersection. Therefore they are placed adjacently, thus the circumference of the polygon does not bend there, so it is not necessarily a vertex.

Since all the edge rows and columns consists of ., we only have to check for each \(1 \le x \lt H, 1 \le y \lt W\), so we don’t really have to worry about referencing out of bounds of \(S\).