grid47 Exploring patterns and algorithms
Sep 15, 2024
7 min read
Solution to LeetCode 529: Minesweeper Problem
You are playing the game Minesweeper. Given an m x n grid, you must reveal the square corresponding to the next click and update the grid according to Minesweeper’s rules. The grid can contain mines (‘M’), empty squares (‘E’), or revealed squares with adjacent mine counts.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D list representing the board and an array of two integers representing the click position.
• Explanation: Here, clicking on an empty square with adjacent mines will reveal the number of adjacent mines or recursively reveal surrounding squares if there are no adjacent mines.
Approach: To solve this problem, we need to recursively reveal squares based on the Minesweeper rules.
Observations:
• The game is based on revealing squares and updating the board recursively.
• We will need to check adjacent squares and recursively reveal empty squares without adjacent mines.
Steps:
• Check if the clicked square is a mine. If it is, set it to 'X'.
• If the clicked square is empty, count adjacent mines. If there are any, set the square to the count of adjacent mines.
• If no adjacent mines are found, change the square to 'B' and recursively reveal adjacent squares.
Empty Inputs:
• The clicked square is already revealed.
Large Inputs:
• The board size is at the maximum allowed.
Special Values:
• The click lands on a corner or edge of the board.
Constraints:
• Ensure no out-of-bounds errors when revealing adjacent squares.
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int m = board.size(), n = board[0].size();
int row = click[0], col = click[1];
if(board[row][col] =='M') {
board[row][col] ='X';
} else {
int cnt =0;
for(int i =-1; i <=1; i++)
for(int j =-1; j <=1; j++) {
if(i ==0&& j ==0) continue;
int x = row + i, y = col + j;
if(x <0|| y <0|| x >= m || y >= n) continue;
if(board[x][y] =='M'|| board[x][y] =='X') cnt++;
}
if (cnt >0) board[row][col] ='0'+ cnt;
else {
board[row][col] ='B';
for(int i =-1; i <=1; i++)
for(int j =-1; j <=1; j++) {
if(i ==0&& j ==0) continue;
int x = row + i, y = col + j;
if(x <0|| y <0|| x >= m || y >= n) continue;
vector<int> arr;
arr.push_back(x);
arr.push_back(y);
if(board[x][y] =='E') updateBoard(board, arr);
}
}
}
return board;
}
