Program to Reveal the positions in Minesweeper
Given a m x n char matrix mat[][] representing the Minesweeper game board. The matrix mat[i][j], uses characters to denote unopened mines (βMβ), unopened empty squares (βEβ), opened blank squares with no adjacent mines (βBβ), opened squares with adjacent mines (digits β1β to β8β), and opened mines (βXβ) and the next click position is given by the integer array click[], where click = [i, j] represents the next click position among all the unopened cells/squares (βMβ or βEβ). The task is to return the board after revealing this position according to the following rules:
- If a mine βMβ is opened, you should change it to βXβ and finish the game.
- If an empty square βEβ with no adjacent mines is revealed, then change it to a revealed blank βBβ and all of its adjacent unrevealed squares should be revealed recursively.
- If an empty square βEβ with at least one adjacent mine is revealed, then change it to a digit (β1β to β8β) representing the number of adjacent mines.
Examples:
Input: mat={βEβ,βEβ,βEβ,βEβ,βEβ},
{βEβ,βEβ,βMβ,βEβ,βEβ},
{βEβ,βEβ,βEβ,βEβ,βEβ},
{βEβ,βEβ,βEβ,βEβ,βEβ}}, click = {3,0}
Output: {{βBβ,β1β²,βEβ,β1β²,βBβ},
{βBβ,β1β²,βMβ,β1β²,βBβ},
{βBβ,β1β²,β1β²,β1β²,βBβ},
{βBβ,βBβ,βBβ,βBβ,βBβ}}
Explanation: At cell {3,0} there is βEβ it is revealed and no adjacent mines so it is changed to βBβ and all the adjacent directions recursively which are βEβ are revealed { {3,1}, {3,2}, {3,3}, {3,4}, {4,1}, {4,2}, {4,3} } are changed to βBβ because they have no adjacent hence they are blank cells, { {0,1}, {1,1}, {2,1}, {2,2}, {2,3}, {1,3}, {0,3} } are adjacent to the above cells that are changed to βBβ so these cells are explored recursively from the cells that are changed to βBβ so these are changed to β1β since they have 1 adjacent mine they are revealed to β1β and no further exploration done.Input: mat = {{βBβ,β1β²,βEβ,β1β²,βBβ},
{βBβ,β1β²,βMβ,β1β²,βBβ},
{βBβ,β1β²,β1β²,β1β²,βBβ},
{βBβ,βBβ,βBβ,βBβ,βBβ}}, click = {1,2}
Output: {{βBβ,β1β²,βEβ,β1β²,βBβ},
{βBβ,β1β²,βXβ,β1β²,βBβ},
{βBβ,β1β²,β1β²,β1β²,βBβ},
{βBβ,βBβ,βBβ,βBβ,βBβ}}
Explanation: At cell {1,2} there is already a mine so change it to βXβ only.
Reveal the positions in Minesweeper using Recursion:
This problem can be solved using the recursion, There are three case :
Case 1: When the cell = βMβ is clicked, change it to βXβ and return the board.
Case 2: When the cell = βEβ is clicked which have adjacent mines , count the adjacent cells in all 8 directions which have mines and assign the number and backtrack to previous cell without more exploration.
Case 3: When the cell = βEβ is clicked which has no adjacent mines, change the current cell to βBβ and recursively do the DFS to all the adjacent 8 directions and reveal them.
Step-by-step approach:
- Initialize a directions array adjacents[][] for exploring all the adjacent 8 directions.
- Check if the current clicked cell is a mine, if it is a mine replace it with βXβ and return the mat[][].
- If the current clicked cell is βEβ then reveal the cell and its adjacent cells based on the adjacent mineCount.
- In the explore function, Initialize a variable mineCounter to 0
- Check in all the 8 directions and count the number of mines
- If there are adjacent mines then assign the cell with the count of mines
- If there are no adjacent mines then assign the cell βBβ as revealed blank cell
- Now recursively check the adjacents to reveal them by doing the dfs
- Perform the dfs to explore the adjacent cells
- Return the mat[][].
Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Adjacents directions array int adjacents[8][2] = { { 1, 1 }, { -1, -1 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, { -1, 1 }, { 1, -1 } }; // Function to do the dfs to the adjacent directions void explore(vector<vector< char > >& mat, int x, int y) { // Initialize a variable mineCounter to 0 int mineCounter = 0; // Check in all the adjacents 8 directions and counts // the number of mines for ( int i = 0; i < 8; i++) { int x1 = x + adjacents[i][0]; int y1 = y + adjacents[i][1]; if (x1 >= 0 && y1 >= 0 && x1 < mat.size() && y1 < mat[0].size() && mat[x1][y1] == 'M' ) mineCounter++; } // If there are adjacent mines then assign the cell with // the count of mines if (mineCounter > 0) { mat[x][y] = mineCounter + '0' ; return ; } // If there are no adjacent mines then assign the cell // 'B' as revealed blank cell mat[x][y] = 'B' ; // Now check the adjacents to reveal them by doing the // dfs for ( int i = 0; i < 8; i++) { int x1 = x + adjacents[i][0]; int y1 = y + adjacents[i][1]; // Validate the adjacent coordinates if (x1 >= 0 && y1 >= 0 && x1 < mat.size() && y1 < mat[0].size() && mat[x1][y1] == 'E' ) // Perform the dfs to the excplore the adjacent // cells explore(mat, x1, y1); } } // Function to implement the mine sweeper vector<vector< char > > MineSweeper(vector<vector< char > >& mat, vector< int >& click) { // Check if the current clicked cell is a mine, if it is // a mine replace it with 'X' and return the mat if (mat[click[0]][click[1]] == 'M' ) { mat[click[0]][click[1]] = 'X' ; return mat; } // If the current cell is 'E' then reveal the cell and // its adjacent cells based on the adjacent mineCount explore(mat, click[0], click[1]); return mat; } // Driver code int main() { vector<vector< char > > mat = { { 'E' , 'E' , 'E' , 'E' , 'E' }, { 'E' , 'E' , 'M' , 'E' , 'E' }, { 'E' , 'E' , 'E' , 'E' , 'E' }, { 'E' , 'E' , 'E' , 'E' , 'E' } }; vector< int > click = { 3, 0 }; vector<vector< char > > res = MineSweeper(mat, click); for ( int i = 0; i < res.size(); i++) { for ( int j = 0; j < res[0].size(); j++) { cout << res[i][j] << " " ; } cout << endl; } return 0; } |
Java
import java.util.*; public class GFG { // Adjacent directions array static int [][] adjacents = { { 1 , 1 }, { - 1 , - 1 }, { 0 , 1 }, { 0 , - 1 }, { 1 , 0 }, { - 1 , 0 }, { - 1 , 1 }, { 1 , - 1 } }; // Function to do the dfs to the // adjacent directions static void explore( char [][] mat, int x, int y) { int mineCounter = 0 ; for ( int i = 0 ; i < 8 ; i++) { int x1 = x + adjacents[i][ 0 ]; int y1 = y + adjacents[i][ 1 ]; if (x1 >= 0 && y1 >= 0 && x1 < mat.length && y1 < mat[ 0 ].length && mat[x1][y1] == 'M' ) { mineCounter++; } } if (mineCounter > 0 ) { mat[x][y] = ( char )(mineCounter + '0' ); return ; } mat[x][y] = 'B' ; for ( int i = 0 ; i < 8 ; i++) { int x1 = x + adjacents[i][ 0 ]; int y1 = y + adjacents[i][ 1 ]; if (x1 >= 0 && y1 >= 0 && x1 < mat.length && y1 < mat[ 0 ].length && mat[x1][y1] == 'E' ) { explore(mat, x1, y1); } } } // Function to implement the mine sweeper static char [][] mineSweeper( char [][] mat, int [] click) { if (mat[click[ 0 ]][click[ 1 ]] == 'M' ) { mat[click[ 0 ]][click[ 1 ]] = 'X' ; return mat; } explore(mat, click[ 0 ], click[ 1 ]); return mat; } // Driver code public static void main(String[] args) { char [][] mat = { { 'E' , 'E' , 'E' , 'E' , 'E' }, { 'E' , 'E' , 'M' , 'E' , 'E' }, { 'E' , 'E' , 'E' , 'E' , 'E' }, { 'E' , 'E' , 'E' , 'E' , 'E' } }; int [] click = { 3 , 0 }; char [][] res = mineSweeper(mat, click); for ( int i = 0 ; i < res.length; i++) { for ( int j = 0 ; j < res[ 0 ].length; j++) { System.out.print(res[i][j] + " " ); } System.out.println(); } } } |
Python3
# Adjacent directions array adjacents = [( 1 , 1 ), ( - 1 , - 1 ), ( 0 , 1 ), ( 0 , - 1 ), ( 1 , 0 ), ( - 1 , 0 ), ( - 1 , 1 ), ( 1 , - 1 )] # Function to do the Depth-First Search (DFS) to explore adjacent directions def explore(mat, x, y): mineCounter = 0 # Check adjacent cells for mines for i in range ( 8 ): x1 = x + adjacents[i][ 0 ] y1 = y + adjacents[i][ 1 ] # Verify boundary conditions and check for mines if (x1 > = 0 and y1 > = 0 and x1 < len (mat) and y1 < len (mat[ 0 ]) and mat[x1][y1] = = 'M' ): mineCounter + = 1 # If adjacent mines are found, update the current cell with the count if mineCounter > 0 : mat[x][y] = str (mineCounter) return # If no adjacent mines are found, mark the cell as 'B' (blank) and continue exploring mat[x][y] = 'B' # Explore adjacent cells recursively for i in range ( 8 ): x1 = x + adjacents[i][ 0 ] y1 = y + adjacents[i][ 1 ] # Verify boundary conditions and explore empty cells ('E') if (x1 > = 0 and y1 > = 0 and x1 < len (mat) and y1 < len (mat[ 0 ]) and mat[x1][y1] = = 'E' ): explore(mat, x1, y1) # Function to implement the mine sweeper def mineSweeper(mat, click): # If the clicked cell contains a mine ('M'), mark it as 'X' if mat[click[ 0 ]][click[ 1 ]] = = 'M' : mat[click[ 0 ]][click[ 1 ]] = 'X' return mat # If the clicked cell is empty ('E'), start the exploration process explore(mat, click[ 0 ], click[ 1 ]) return mat # Driver code mat = [[ 'E' , 'E' , 'E' , 'E' , 'E' ], [ 'E' , 'E' , 'M' , 'E' , 'E' ], [ 'E' , 'E' , 'E' , 'E' , 'E' ], [ 'E' , 'E' , 'E' , 'E' , 'E' ]] click = [ 3 , 0 ] # Clicked cell coordinates res = mineSweeper(mat, click) # Display the resulting matrix after mineSweeper execution for i in range ( len (res)): for j in range ( len (res[ 0 ])): print (res[i][j], end = " " ) print () |
C#
using System; using System.Collections.Generic; class Program { // Adjacents directions array static int [, ] adjacents = { { 1, 1 }, { -1, -1 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, { -1, 1 }, { 1, -1 } }; // Function to do the dfs to the adjacent directions static void Explore(List<List< char > > mat, int x, int y) { // Initialize a variable mineCounter to 0 int mineCounter = 0; // Check in all the adjacents 8 directions and // counts the number of mines for ( int i = 0; i < 8; i++) { int x1 = x + adjacents[i, 0]; int y1 = y + adjacents[i, 1]; if (x1 >= 0 && y1 >= 0 && x1 < mat.Count && y1 < mat[0].Count && mat[x1][y1] == 'M' ) mineCounter++; } // If there are adjacent mines then assign the cell // with the count of mines if (mineCounter > 0) { mat[x][y] = ( char )(mineCounter + '0' ); return ; } // If there are no adjacent mines then assign the // cell 'B' as revealed blank cell mat[x][y] = 'B' ; // Now check the adjacents to reveal them by doing // the dfs for ( int i = 0; i < 8; i++) { int x1 = x + adjacents[i, 0]; int y1 = y + adjacents[i, 1]; // Validate the adjacent coordinates if (x1 >= 0 && y1 >= 0 && x1 < mat.Count && y1 < mat[0].Count && mat[x1][y1] == 'E' ) // Perform the dfs to explore the adjacent // cells Explore(mat, x1, y1); } } // Function to implement the mine sweeper static List<List< char > > MineSweeper(List<List< char > > mat, List< int > click) { // Check if the current clicked cell is a mine, if // it is a mine replace it with 'X' and return the // mat if (mat[click[0]][click[1]] == 'M' ) { mat[click[0]][click[1]] = 'X' ; return mat; } // If the current cell is 'E' then reveal the cell // and its adjacent cells based on the adjacent // mineCount Explore(mat, click[0], click[1]); return mat; } // Driver code static void Main() { List<List< char > > mat = new List<List< char > >{ new List< char >{ 'E' , 'E' , 'E' , 'E' , 'E' }, new List< char >{ 'E' , 'E' , 'M' , 'E' , 'E' }, new List< char >{ 'E' , 'E' , 'E' , 'E' , 'E' }, new List< char >{ 'E' , 'E' , 'E' , 'E' , 'E' } }; List< int > click = new List< int >{ 3, 0 }; List<List< char > > res = MineSweeper(mat, click); for ( int i = 0; i < res.Count; i++) { for ( int j = 0; j < res[0].Count; j++) { Console.Write(res[i][j] + " " ); } Console.WriteLine(); } } } |
Javascript
// Adjacents directions array const adjacents = [ [1, 1], [-1, -1], [0, 1], [0, -1], [1, 0], [-1, 0], [-1, 1], [1, -1] ]; // Function to do the dfs to the adjacent directions function explore(mat, x, y) { let mineCounter = 0; // Check in all the adjacent 8 directions and count the number of mines for (let i = 0; i < 8; i++) { const x1 = x + adjacents[i][0]; const y1 = y + adjacents[i][1]; if ( x1 >= 0 && y1 >= 0 && x1 < mat.length && y1 < mat[0].length && mat[x1][y1] === 'M' ) { mineCounter++; } } if (mineCounter > 0) { mat[x][y] = (mineCounter + '' ); return ; } mat[x][y] = 'B' ; for (let i = 0; i < 8; i++) { const x1 = x + adjacents[i][0]; const y1 = y + adjacents[i][1]; if ( x1 >= 0 && y1 >= 0 && x1 < mat.length && y1 < mat[0].length && mat[x1][y1] === 'E' ) { explore(mat, x1, y1); } } } // Function to implement the mine sweeper function mineSweeper(mat, click) { if (mat[click[0]][click[1]] === 'M' ) { mat[click[0]][click[1]] = 'X' ; return mat; } explore(mat, click[0], click[1]); return mat; } // Driver code const mat = [ [ 'E' , 'E' , 'E' , 'E' , 'E' ], [ 'E' , 'E' , 'M' , 'E' , 'E' ], [ 'E' , 'E' , 'E' , 'E' , 'E' ], [ 'E' , 'E' , 'E' , 'E' , 'E' ] ]; const click = [3, 0]; const res = mineSweeper(mat, click); for (let i = 0; i < res.length; i++) { console.log(res[i].join( ' ' )); } |
B 1 E 1 B B 1 M 1 B B 1 1 1 B B B B B B
Time Complexity: O(n*m) where n is the number of rows and m is the number of columns
Auxiliary Space: O(n*m) where n is the number of rows and m is the number of columns