I had trouble finding any solutions online, so I'm sharing this here for future reference.

A curious observation: since the map is good, we can always find a # such that removing it keeps the map good. The possible configurations are the following three patterns and their rotations (where x marks the removed #):

?## ?#? ...
.x# .x. .x.
..? ... ...

Also notice that each such deletion either leaves $dis(S,F)$ unchanged or decreases it by $2$. Therefore, as long as the parity and the bounds of $d$ (Manhattan distance, and the initial distance) are correct, it is valid.

We can maintain the removal process with a queue: each time a cell is deleted, we check its neighbouring cells to see if they can be deleted, and enqueue them if so.

Since $dis(S,F)$ is monotonic, we can binary search on the number of deleted cells. The overall time complexity is $O(nm \log nm)$.