これは、Google Code Jam 予選ラウンドの問題です (現在は終了しています)。この問題を解決するには？
注: 回答で説明した方法とは異なる方法がある場合は、それを共有してください。この問題を解決するさまざまな方法についての知識を広げることができます。
マインスイーパは、1980 年代に人気を博したコンピュータ ゲームで、現在でも Microsoft Windows オペレーティング システムの一部のバージョンに含まれています。この問題も同様の考え方ですが、マインスイーパをプレイしたことがあるとは限りません。
この問題では、同じセルのグリッドでゲームをプレイしています。各セルの内容は、最初は非表示になっています。グリッドの M 個の異なるセルに M 個の地雷が隠されています。他のセルには地雷が含まれていません。任意のセルをクリックして表示できます。明らかにされたセルに鉱山が含まれている場合、ゲームは終了し、負けます。それ以外の場合、公開されたセルには、地雷を含む隣接セルの数に対応する 0 から 8 までの数字が含まれます。2 つのセルがコーナーまたはエッジを共有している場合、2 つのセルは隣接しています。さらに、公開されたセルに 0 が含まれている場合、公開されたセルのすべての隣接セルも再帰的に自動的に公開されます。地雷を含まないすべてのセルが表示されると、ゲームは終了し、勝利します。
たとえば、ボードの初期設定は次のようになります (「*」は鉱山を示し、「c」は最初にクリックされたセルです)。
*..*...**.
....*.....
..c..*....
........*.
..........
クリックされたセルに隣接する地雷がないため、表示されると 0 になり、隣接する 8 つのセルも表示されます。このプロセスが続き、次のボードが作成されます。
*..*...**.
1112*.....
00012*....
00001111*.
00000001..
この時点で、地雷を含まない未公開のセル (「.」文字で示される) がまだあるため、プレイヤーはゲームを続行するためにもう一度クリックする必要があります。
できるだけ早くゲームに勝ちたい。ワンクリックで勝つことほど速いものはありません。ボードのサイズ (R x C) と隠された地雷の数 M を考えると、1 回のクリックで勝つことは可能 (可能性は低いですが) でしょうか? クリックする場所を選択できます。可能であれば、出力セクションの仕様に従って、有効な地雷の構成とクリックの座標を印刷します。それ以外の場合は、「不可能」と出力します。
私の試した解決策：
したがって、解決策として、各非鉱山ノードが他の非鉱山ノードと一緒に 3x3 マトリックス内にあるか、ノードがグリッドの端にある場合は 3x2 または 2x2 マトリックス内にあることを確認する必要があります。これを 0Matrix と呼びましょう。したがって、0Matrix 内の任意のノードには、すべての非鉱山隣接ノードがあります。
まず、必要な鉱山が少ないか、空のノードが少ないかを確認します
if(# mines required < 1/3 of total grid size)
// Initialize the grid to all clear nodes and populate the mines
foreach (Node A : the set of non-mine nodes)
foreach (Node AN : A.neighbors)
if AN forms a OMatrix with it's neighbors, continue
else break;
// If we got here means we can make A a mine since all of it's neighbors
// form 0Matricies with their other neighbors
// End this loop when we've added the number of mines required
else
// We initialize the grid to all mines and populate the clear nodes
// Here I handle grids > 3x3;
// For smaller grids, I hard coded the logic, eg: 1xn grids, you just populate in 1 dimension
// Now we know that the # clear nodes required will be 3n+2 or 3n+4
// eg: if a 4x4 grid need 8 clear nodes : 3(2) + 2
For (1 -> num 3's needed)
Add 3 nodes going horizontally
When horizontal axis is filled, add 3 nodes going vertically
When vertical axis is filled, go back to horizontal then vertical and so on.
for(1 -> num 2's needed)
Add 2 nodes going horizontally or continuing in the direction from above
When horizontal axis is filled, add 2 nodes going vertically
たとえば、8 つのクリーン ノードを必要とする 4x4 グリッドがあるとします。手順は次のとおりです。
// Initial grid of all mines
* * * *
* * * *
* * * *
* * * *
// Populating 3's horizontally
. * * *
. * * *
. * * *
* * * *
. . * *
. . * *
. . * *
* * * *
// Populating 2's continuing in the same direction as 3's
. . . *
. . . *
. . * *
* * * *
別の例: 11 個のクリア ノードが必要な 4x4 グリッド。出力：
. . . .
. . . .
. . . *
* * * *
別の例: 14 個のクリア ノードが必要な 4x4 グリッド。出力：
// Insert the 4 3's horizontally, then switch to vertical to insert the 2's
. . . .
. . . .
. . . .
. . * *
これで、完全に入力されたグリッドができ、(0, 0) をクリックすると 1 クリックで解決できます。
私のソリューションはほとんどのケースで機能しますが、提出に合格しませんでした (225 ケースの出力ファイル全体を確認しました)。