Leetcode 130: Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.

非常感谢这个题目， 这个题目不仅考察了思考问题的方式， 也考察了dfs 的 iteration的写法， 以前觉得是个很难的问题，但是实现后发现其实dfs 从recursion 到iteration的改写很容易啊！跟写BFS的queue一样啊！只要每次把stack的顶部元素pop出来进行expand就可以了。
这个题目的思考问题方式也感觉是给大脑的一个brain storm， 要想找出所有被X包围的O， 最先想到的是从O出发，进行dfs, explore O， 如果O到了外围，那么这条路上的O是没有被X包围的，但是这样做需要从外围的O找到里面去，不是很容易吧，如果换个思路，直接从外围的O进行DFS往里面explore呢，那么跟外围的O连通的O都能找到啊！如果我们把能跟外围O都能找到的O做一个特殊标记‘#’， 那么矩阵里面还剩下的O不就是被X包围的O了嘛！这样这道题目就解决了！
但是还有一个小细节需要注意， 最后将内部的O变成X的同时，需要把之前做了特殊标记的O变成原来的O.

时间复杂度： O（n ^ 2） 空间复杂度： O（n）
这个题目还需要注意的一点是：如果dfs用recursion来写，当数据很大的时候会造成run time error, 这意味着recursion 调用stack超出了范围，造成了stack 溢出！

class Solution {
private:
    void dfs(vector<vector<char>> &board, int i, int j) {
        stack<pair<int, int>> explore;
        explore.push(make_pair(i, j));
        while (!explore.empty()) {
            pair<int, int> tmp = explore.top();
            explore.pop();
            // not visited, visit
            if (board[tmp.first][tmp.second] != '#') {
                board[tmp.first][tmp.second] = '#';
                if (tmp.first +1 < board.size() && board[tmp.first+1][tmp.second] == 'O') explore.push(make_pair(tmp.first+1, tmp.second));
                if (tmp.first-1 >= 0 && board[tmp.first-1][tmp.second] == 'O') explore.push(make_pair(tmp.first-1, tmp.second));
                if (tmp.second-1 >= 0 && board[tmp.first][tmp.second-1] == 'O') explore.push(make_pair(tmp.first, tmp.second-1));
                if (tmp.second+1 < board[0].size() && board[tmp.first][tmp.second+1] == 'O') explore.push(make_pair(tmp.first, tmp.second+1));
            }
        }
    }
public:
    void solve(vector<vector<char>>& board) {
        if (board.size() < 3 || board[0].size() < 3) return;
        for (int i = 0; i < board.size(); i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][board[0].size()-1] == 'O') {
                dfs(board, i, board[0].size()-1);
            }
        }
        for (int i = 1; i < board[0].size()-1; i++) {
            if (board[0][i] == 'O') {
                dfs(board, 0, i);
            }
            if (board[board.size()-1][i] == 'O') {
                dfs(board, board.size()-1, i);
            }
        }
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size();j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
        return;
    }
};