C++ DFS solution, easy to understand


  • 4
    N
    class Solution {
    public:
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
            if(board[click[0]][click[1]] == 'M'){
                board[click[0]][click[1]] = 'X';
                return board;
            }
            reveal(board,click[0],click[1]);
            return board;
        }
        
        bool inboard(const vector<vector<char>>& board, int x, int y){
            return ( x>=0 && x<board.size() && y>=0 && y<board[0].size() );
        }
        
        void reveal(vector<vector<char>>& board, int x, int y){
            if(!inboard(board,x,y)) return;
            if(board[x][y] == 'E'){
                //search 8 adjacent squares
                int count = 0;
                if(inboard(board,x-1,y-1) && board[x-1][y-1] == 'M') count++;
                if(inboard(board,x-1,y  ) && board[x-1][y  ] == 'M') count++;
                if(inboard(board,x-1,y+1) && board[x-1][y+1] == 'M') count++;
                if(inboard(board,x  ,y-1) && board[x  ][y-1] == 'M') count++;
                if(inboard(board,x  ,y+1) && board[x  ][y+1] == 'M') count++;
                if(inboard(board,x+1,y-1) && board[x+1][y-1] == 'M') count++;
                if(inboard(board,x+1,y  ) && board[x+1][y  ] == 'M') count++;
                if(inboard(board,x+1,y+1) && board[x+1][y+1] == 'M') count++;
    
                if(count>0)
                    board[x][y] = '0'+count;
                else{
                    board[x][y] = 'B';
                    reveal(board,x-1,y-1);
                    reveal(board,x-1,y  );
                    reveal(board,x-1,y+1);
                    reveal(board,x  ,y-1);
                    reveal(board,x  ,y+1);
                    reveal(board,x+1,y-1);
                    reveal(board,x+1,y  );
                    reveal(board,x+1,y+1);
                }
            }
        }
    };
    

  • 3
    H

    it can be more easy like that.

    class Solution {
    public:
    	vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
    		if (board[click[0]][click[1]] == 'M') {
    			board[click[0]][click[1]] = 'X';
    			return board;
    		}
    		dfs(board, click[0], click[1]);
    		return board;
    	}
    	void dfs(vector<vector<char> > &b, int x, int y) {
    		if (!judge(x, y, b))return;
    		vector<vector<int> > v = { {1,-1},{ 1,0 },{ 1,1 },{ -1,-1 },{ -1,0 },{ -1,1 },{ 0,-1 },{ 0,1 } };
    		int count = 0;
    		if (b[x][y] == 'E') {
    			for (int i = 0; i < 8; i++) {
    				if (judge(x + v[i][0], y + v[i][1], b) && b[x + v[i][0]][y + v[i][1]] == 'M')
    					count++;
    			}
    			if (count > 0)
    				b[x][y] = '0' + count;
    			else {
    				b[x][y] = 'B';
    				for (int i = 0; i < 8; i++) {
    					dfs(b, x + v[i][0], y + v[i][1]);
    				}
    			}
    		}
    	}
    	bool judge(int x, int y,vector<vector<char> > b) {
    		return x >= 0 && x < b.size() && y >= 0 && y < b[0].size();
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.