練習のために、私はインタビューストリートの問題を解決し始めました。このクイーンズオンボードの問題に出くわしました。
クイーンズオンボード (50 ポイント)
N * M のチェス盤があり、いくつかの正方形がブロックされています。2 つのクイーンが互いに攻撃しないように、1 つまたは複数のクイーンをボードに配置できる方法はいくつありますか? ブロックされた正方形を通過せずに、水平、垂直、または斜めに移動して、一方が他方に到達できる場合、2 つのクイーンが互いに攻撃します。1 つのマスに配置できるクイーンは 1 つまでです。ブロックされたマスにクイーンを置くことはできません。
入力: 最初の行にはテスト ケースの数 T が含まれます。T 個のテスト ケースが続きます。各テスト ケースには、最初の行に整数 N と M が含まれています。次の N 行には、ボードを表す M 文字が含まれています。「#」はブロックされた四角を表し、「.」は「.」を表します。ブロックされていない正方形を表します。
出力: 各テスト ケースに必要な回答を含む T 行を出力します。答えは非常に大きくなる可能性があるため、1000000007 を法として出力します。
https://www.interviewstreet.com/challenges/dashboard/#problem/4e904d63c5069
この問題を解決するのに最適なアルゴリズムは何ですか?
ありがとうございました。