[LeetCode] 529. Minesweeper

https://leetcode.com/contest/leetcode-weekly-contest-21/problems/minesweeper/

Solution:
This question is pretty straightforward. May consider the BSF strategy. (DSF also works, but usually the code length will be a little bit longer for "diffusion" problems in a 2D matrix). Also need a visit matrix to record the visiting status: for each element, if it has been visited(or pushed into a queue), then no more is needed. Without this visit matrix, infinity loop may occur. See code below:

Code:

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board.empty() || board.front().empty()) return board;
        int x=click[0], y=click[1];
        if(board[x][y]=='M'){
            board[x][y]='X';
            return board;
        }
        int m = board.size(), n = board.front().size();
        queue<pair<int, int>> q;
        vector<vector<bool>> visit(m, vector<bool>(n, true));
        q.push(make_pair(x, y));
        visit[x][y]=false;
        vector<vector<int>> d={{0,1},{1,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,0},{1,-1}};
        while(q.size()){
            pair<int, int> t=q.front();
            q.pop();
            int ct=0;
            for(auto a:d){
                int tx=t.first+a[0], ty=t.second+a[1];
                if(tx>=0&&tx<m&&ty>=0&&ty<n){
                    if(board[tx][ty]=='M') ++ct;
                }
            }
            if(ct==0) {
                board[t.first][t.second]='B';
                for(auto a:d){
                    int tx=t.first+a[0], ty=t.second+a[1];
                    if(tx>=0&&tx<m&&ty>=0&&ty<n){
                        if(visit[tx][ty]&&board[tx][ty]=='E') {
                            q.push(make_pair(tx, ty));
                            visit[tx][ty]=false;
                        }
                    }
                }
            }
            else board[t.first][t.second]=ct+'0';
        }
        return board;
    }
};