盤面を 2 進法で表された整数だと考えて処理すると、実装が簡単になり、並列計算の分だけ計算量も小さくなります。 本問では 2 次元盤面なので、例えば右端に番兵を付けて \(H \times (W + 1)\) ビットの整数で表すと良いでしょう。なお本問の制約だと \(64\) ビット整数に収まらないので、 \(128\) ビット整数を使うか Python のような多倍長整数を使う必要があります。

探索の方法は、再帰 DFS や、順列をすべて列挙する方法などが考えられます。 後者の場合、 Python では itertools.permutations が便利です。

• AC コード （Python）再帰 DFS

• AC コード （Python）itertools の permutations を使用

【参考】 過去の類題（2 次元盤面を 2 進法の整数とみなして処理する方法が使える問題）

• 問題 解説

• 問題 解説