지뢰 찾기

(2020 년 12 월 25 일)

이전에 지뢰 찾기를 해본 적이 있습니까? 글쎄요, 모두가 우리 어린 시절에 그 게임을 해본 적이 있다고 믿습니다. 그러나 모든 사람이 그 멋진 게임의 논리를 아는 것은 아닙니다. 이 게시물을 위해 저와 함께 있고 제가 당신을 위해 더 간단하게 만들고 당신은 그것을 좋아할 것이라고 믿습니다.

시작합시다!

지뢰 찾기 게임에는 세 가지 유형이 있습니다. 셀, 즉 플래그가 지정된 셀 (내 또는 폭탄이 포함 된 셀), 클릭 가능한 덮개가있는 셀, 이미 노출 된 덮개가없는 셀.

처음에는 임의의 셀을 클릭 할 수 있습니다. 광산, 게임이 끝났습니다. 클릭 한 셀에 숫자가 있으면이 셀에 최대 주변에있는 많은 광산이 있음을 나타냅니다.

p>

셀의 가능한 이웃

셀에는 8 개의 이웃이 있습니다.

그리드 및 주변 이웃의 위치 (x, y)에있는 셀

다음에 숫자가있는 셀의 예를 살펴 보겠습니다.

중앙 셀에는 숫자 1이 있습니다. 즉, 최소한 하나의 광산은 주변 이웃입니다.
이것은 가능한 광산 위치 일 수 있으며 가능한 올바른 그리드를 나타냅니다.
셀에 1이 있으므로 mi가 1 개만 있음을 의미합니다. ne 인접하지만 여기에 두 개의 광산이 표시됩니다. 그래서 이것은 불가능합니다. 이것은 잘못된 그리드입니다.

마찬가지로 숫자가있는 두 셀의 예입니다.

유효합니다. 두 셀 모두 주변에 1 개의 광산 만있을 수 있으며이 광산은 두 광산에 인접 해 있습니다.
유효하지 않습니다. 두 셀 모두 주변 광산을 1 개만 가질 수 있지만 여기서는 두 셀 모두 이웃에 인접한 광산 두 개를 가지고 있습니다.

이제 논리를 이해했을 것입니다. 지뢰 찾기 게임 뒤에. 한 번의 클릭 위치가 주어지고 가능한 한 지뢰 찾기 게임의 셀을 탐색해야한다고 가정합니다.

문제 설명 (출처 — Leetcode)

게임 보드를 나타내는 2D 문자 매트릭스 M 미공개 내, E 미공개 빈 사각형, B 공개 인접한 (위, 아래, 왼쪽, 오른쪽 및 4 개의 대각선 모두) 광산이없는 빈 사각형, digit ( 1~ 8)는이 공개 된 정사각형, 마지막으로 X 공개

이제 모든 중에서 다음 클릭 위치 (행 및 열 색인)가 주어집니다. 미공개 사각형 ( M또는 E), 다음 규칙에 따라이 위치를 공개 한 후 보드를 반환합니다.

지뢰 ( M)가 공개되면 게임이 종료됩니다. X로 변경합니다.

인접 지뢰가 없음 이 드러난 다음 공백 ( B)과 인접한 모든 공개되지 않은 사각형은 재귀 적으로 표시되어야합니다.

적어도 하나의 인접한 광산 이 공개 된 다음 인접한 광산의 수를 나타내는 숫자 ( 1에서 8)로 변경합니다.

더 이상 사각형이 표시되지 않을 때 보드를 반환합니다.

Depth First Search — 자명 코드

//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 ) 재귀를위한 스택 공간

여러분 여러분이이 기사를 귀중하게 생각하기를 바랍니다. 그래도 질문이 있으시면 아래 댓글 섹션에서 토론하실 수 있습니다.

이 블로그에 시간을 할애 해 주셔서 감사합니다.