この問題はBFSの応用で解くことができます。現在のマスの白黒の状態 \(2^{HW}\) 通りと、現在いるマス \(HW\) 通りの組み合わせを状態としてBFSを行えばよいです。

ありえる状態が \(HW2^{HW}\) 通り、各状態から取りうる行動は上下左右への移動の \(4\) 通りであることから、\(O(HW2^{HW})\) 時間でこの問題を解くことができます。

なお、マスの状態を適切に整数にエンコードすると実装が楽になる場合があります。

####     1111
#...     1000
#... --> 1000 --> 1111100010001000
#...     1000

例：白黒を01に置き換え、グリッドを1列に並べ直したものを2進法で表された値として解釈する