マインスイーパ

2020年12月25日)

以前に掃海艇をプレイしたことがありますか?ええと、私はそう信じています、誰もが私たちの子供時代にそのゲームをプレイしました。しかし、誰もがその素晴らしいゲームの背後にある論理を知っているわけではありません。この投稿のために私と一緒にいて、私があなたのためにそれをより簡単にし、あなたがそれを好きになると信じてください。

始めましょう!

マインスイーパゲームには、3つのタイプがありますセル、つまりフラグが立てられたセル(地雷または爆弾を含むセル)、クリック可能なカバーされたセル、既に公開されているカバーされていないセル。

最初は、任意のランダムセルをクリックできますが、残念ながらクリックできます。鉱山、あなたのゲームは終わりました。クリックしたセルに番号が付いている場合は、このセルに最大でこれらの多くの地雷が周囲にあることを示しています。

セルの可能な隣接セル

セルには8つの隣接セルがあります

グリッド内の位置(x、y)および周囲の隣接セル

に番号が付いているセルの例を見てみましょう。

中央のセルには1番があります。つまり、少なくとも最大で周囲の隣人に1つの鉱山があります。
これは地雷の位置である可能性があり、正しいグリッドの可能性を表しています
セルには1が含まれているため、1マイルしかないことを意味しますそれに隣接していますが、ここでは2つの鉱山が示されています。したがって、これは不可能です。これは正しくないグリッドです。

同様に、2つのセルに番号が付いている例。

これは有効です。両方のセルは、周囲の地雷を1つだけ持つことができ、この地雷は両方の地雷に隣接しています。
これは無効です。どちらのセルにも周囲の地雷は1つしかありませんが、ここでは両方のセルの隣に2つの隣接する地雷があります。

これで、ロジックを理解できたと思います。マインスイーパゲームの背後にあります。ワンクリックの位置が与えられ、マインスイーパゲームのセルを可能な限り探索する必要があるとします。

問題の説明(出典— Leetcode)

与えられたゲームボードを表す2D文字マトリックス。 M 未公開鉱山、 E 未公開空の正方形、 B 明らかにされた隣接する(上、下、左、右、および4つの対角線すべて)地雷がない空白の正方形、 Digit ( 1から 8)は、このに隣接する地雷の数を表します正方形、最後に X 明らかにされた鉱山。

これで、すべてのの中で次のクリック位置(行と列のインデックス)が与えられました。明らかにされていない正方形(「M」または「E」)、次のルールに従ってこの位置を明らかにした後、ボードを返します。

地雷(「M」)が明らかになった場合、ゲームは終了します— X に変更します。

隣接する地雷は表示されませんが表示されたら、表示された空白( B)と隣接するすべての非公開正方形は再帰的に公開する必要があります。

少なくとも1つの隣接する地雷が表示されたら、隣接する地雷の数を表す数字(「1」から「8」)に変更します。

正方形が表示されなくなったらボードを返却します。

深さ優先探索—自明のコード

//all the possible 8 directions around a cell
private static int[] xdir = new int[]{-1, 1, -1, 1, -1, 1, 0, 0};
private static int[] ydir = new int[]{0, 0, -1, -1, 1, 1, -1, 1};
//checking if the adjacent position is a valid position or not
private boolean isValid(int newRow, int newCol, int rows, int cols){
return newRow>=0 && newRow=0 && newCol}

クリック後にボードを更新する機能

//function to update the board based on the click
public char[][] updateBoard(char[][] board, int[] click) {
int rows = board.length;
int cols = board[0].length;

//if the click position is revealed or unrevealed mine, change it to revealed mine i.e. X and return the board as the game is over
if(board[click[0]][click[1]]=="M" || board[click[0]][click[1]]=="X"){
board[click[0]][click[1]] = "X";
return board;
}

//if the click position has an unrevealed cell, find the number of mines adjacent to it
int mines = 0;
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=="M"){
mines++;
}
}

//if there is at least one mine adjacent to current click position, then update the board click position with the number of adjacent mines
//and in such case we won"t explore any further from current cell according to problem constraint and just return

if(mines>0){
board[click[0]][click[1]] = Character.forDigit(mines, 10);
return board;
}

//if there is no adjacent mine to the current click position, then mark this cell as revealed black cell
board[click[0]][click[1]] = "B";

//explore the adjacent valid unexplored cells which don"t have mine - DFS from current click position for all the valid cells
for(int i=0; i<8; i++){
int newRow = click[0]+xdir[i];
int newCol = click[1]+ydir[i];

if(isValid(newRow, newCol, rows, cols) && board[newRow][newCol]=="E"){
updateBoard(board, new int[]{newRow, newCol});
}
}

//return the final board
return board;
}

複雑性分析

時間計算量:最悪の場合O(m * n)、ここでmは行数でありnは列の数です。クリック位置からグリッド上でDFSを実行しています

スペースの複雑さ: O(m * n )再帰用のスタックスペース

皆さんこの記事がお役に立てば幸いです。 それでも質問がある場合は、下のコメントセクションで必ず話し合うことができます。

このブログに時間を割いていただきありがとうございます。