← All solutions

This problem can be solved by the standard trick of coordinate compression. Let us illustrate this using the 8 × 8 example grid given in the problem. Note that, with respect to being a stuck square, the x-coordinates 4 to 7 are equivalent since no wall starts or ends within this range. Similarly, the y-coordinates 0 to 1 are also equivalent. This means that the grid can be compressed to a 7 × 5 grid. The compressed grid is equivalent to the old one except that each cell in the compressed grid correspond to potentially many cells in the old grid – the lower right corner in this grid corresponds to the original 8 blocked cells.

In general, when doing this compression, the widths and heights of the compressed grid can be at most 2w + 1 ≤ 2001 which makes it feasible to simply go through the entire grid to find the stuck squares.