(DFS, BFS) [LintCode] Factorization

class Solution {
public:
    /*
     * @param board: board a 2D board containing 'X' and 'O'
     * @return: nothing
     */
    void surroundedRegions(vector<vector<char>> &board) {
        // write your code here
        if(board.empty() || board[0].empty())
            return;
        int n = board.size(), m = board[0].size();
        vector<vector<int>> mark(n, vector<int>(m, 0));    //记录每个格子的No
        vector<bool> surrounded(n*m+1 , true);    //记录这片区域号No是否被X环绕
        int No=0;   //记录一片联通的区域号
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]=='O' && mark[i][j]==0){
                    No++;
                    bfs(board, mark, surrounded, No, i, j);
                    mark[i][j] = No;
                }
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] == 'O' && surrounded[mark[i][j]])
                //被X环绕
                    board[i][j] = 'X';
            }
        }
        
    }
    
    void bfs(vector<vector<char>> &board, vector<vector<int>>& mark, vector<bool>& surrounded, int No, int x, int y ){
        int row = board.size(),col = board[0].size();
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, -1, 0, 1};
        queue<int> qx;
        queue<int> qy;
        qx.push(x);
        qy.push(y);
        //mark[x][y] = No;
        
        while(!qx.empty()){
            int ox = qx.front();
            int oy = qy.front();
            qx.pop();
            qy.pop();
            
            if(ox == 0 || ox == row-1 || oy == 0 ||oy == col-1)
                //碰到边界，说明没有被X包围
                surrounded[No] = false;   //把这块区域No标记为false
            
            for(int i=0; i<4; i++){
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                if(nx>=0 && nx<row && ny>=0 && ny<col && mark[nx][ny]==0 && board[nx][ny]=='O'){
                    mark[nx][ny] = No;
                    qx.push(nx);
                    qy.push(ny);
                }
            }
        }

    }
};

class Solution {
public:
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    static const int inf = 2147483647;
    int n, m;
    void wallsAndGates(vector<vector<int>> &rooms) {
        // write your code here
        if(rooms.empty() || rooms[0].empty())
            return;
        n = rooms.size(), m = rooms[0].size();
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, -1, 0, 1};
        
        queue<int> qx;
        queue<int> qy;
        
        //多源点多终点最短路径：将所有的gate入队列
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(rooms[i][j] == 0){
                    qx.push(i);
                    qy.push(j);
                }
            }
        }
        
        while(!qx.empty()){
            int ox = qx.front();
            int oy = qy.front();
            qx.pop();
            qy.pop();
            for(int i=0; i<4; i++){
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m && rooms[nx][ny]==inf){
                    qx.push(nx);
                    qy.push(ny);
                    rooms[nx][ny] = rooms[ox][oy] + 1;
                }
            }
        }
    }
};

class Solution {
public:
    /**
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> ans;
    
    //当前层数x；总共层数l，中间状态str, 
    void dfs(int x, int l, string str, string digits, vector<string>& phone){
        //退出条件
        if(x == l){
            ans.push_back(str);
            return;
        }
        
        int num = digits[x] - '0';
        for(int i=0; i<phone[num].size(); i++){
            //数字num有多少种拓展情况
            dfs(x+1, l, str+phone[num][i], digits, phone);
        }
    }
    
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> phone = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits.empty())
            return ans;
        dfs(0, digits.size(), "", digits, phone);
        return ans;
    }
};