Leetcode 529. Minesweeper 踩地雷 (BFS & DFS )

這題我一開始是用 DFS 實作,但不知道是哪裡設計不好,碰到了 stack overflow 。

以下是用 queue 來實作 BFS

public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.add(click);

while(!queue.isEmpty()){
int[] cell = queue.poll();
int row = cell[0], col = cell[1];

// Queue<int[]> q2 = new LinkedList<>();
if(board[row][col] == 'M'){
board[row][col] = 'X';
}else if(board[row][col] =='E'){
int count = 0;
// q2.clear();
for(int i = row-1 ; i < row+2 ; i++){
for(int k = col-1 ; k < col+2 ; k++){
if( i==row && k==col )continue;
if (i < 0 || i >= m || k < 0 || k >= n) continue;
if(board[i][k] == 'M' || board[i][k] == 'X' )count++;
// if (board[i][k] == 'E') {
// q2.add(new int[] {i, k});
// }
}
}
if(count > 0){
board[row][col] = (char)(count + '0');
}else{
board[row][col] = 'B';
// queue.addAll(q2);
for(int i = row-1 ; i < row+2 ; i++){
for(int k = col-1 ; k < col+2 ; k++){
if( i==row && k==col )continue;
if (i < 0 || i >= m || k < 0 || k >= n) continue;
if (board[i][k] == 'E') {
queue.add(new int[] {i, k});
}
}
}
}
}
}

return board;
}

不過不幸的是,效能大概是倒數30%的。所以我想看看能不能夠改進效能。

有注意到的 這邊有幾行註解,因為我發現其實有跑兩次迴圈 在做類似的事情,所以我把它再多一個queue來在上面的時候先記錄,如果確定這一格是blank就把 q2 加到 主 queue當中。

但是效能依舊沒有改變。

所以我就想說不如改試試看用DFS 好了。

public class Solution {
public char[][] updateBoard(char[][] board, int[] click) {
int m = board.length, n = board[0].length;
int row = click[0], col = click[1];

if (board[row][col] == 'M') { // Mine
board[row][col] = 'X';
}
else { // Empty
// Get number of mines first.
int count = 0;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}

if (count > 0) { // If it is not a 'B', stop further DFS.
board[row][col] = (char)(count + '0');
}
else { // Continue DFS to adjacent cells.
board[row][col] = 'B';
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
}
}
}
}
return board;
}
}

發現結果出奇的好,最好會到90% 最少也有 50% 。不知道是不是因為上面一直頻繁的在讀queue導致效能不夠好。

所以我想說來把它改成 function化一些(其實我一開始實作就是這樣不過不知道為啥 stack overflow),另外我改用stack實作的速度會變成不是很理想(後30%)。

最後我把地雷的數數分離出來

private int countMines(int row,int col,char[][] board){
int count = 0,m = board.length, n = board[0].length;
for (int i = -1; i < 2; i++) {
for (int j = -1; j < 2; j++) {
if (i == 0 && j == 0) continue;
int r = row + i, c = col + j;
if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
if (board[r][c] == 'M' || board[r][c] == 'X') count++;
}
}
return count;
}
Show your support

Clapping shows how much you appreciated Bear熊’s story.