[LeetCode] Surrounded Regions

Surrounded RegionsFeb 22

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 .

For example,

X X X X
X O O X
X X O X
X O X X

 

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

 

 

 

class Solution {
public:
    void solve(vector<vector<char>> &board) {
    if (board.size() == 0 ) return ;
    vector<vector<bool> > flag(board.size());
    for (int i = 0; i < board.size(); ++i) {
        flag[i].resize(board.size(), false);
    }
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};
    char xxx = 'X';
    for (int i = 1; i < board.size() - 1; ++i) {
        for (int j = 1; j < board.size() - 1; ++j) {
            if (flag[i][j]) continue;
            // flood fill
            if (board[i][j] == 'O') {
                set<pair<int, int> > s;
                queue<int> q;
                s.insert(make_pair(i, j));
                flag[i][j] = true;
                 q.push(i);
                q.push(j);
                bool is_fill = true;
                while (!q.empty()) {
                    int x = q.front(); q.pop();
                    int y = q.front(); q.pop();
                     for (int k = 0; k < 4; ++k) {
                        if (x+dx[k] < 0 || x+dx[k] >= board.size() || 
                                y+dy[k] < 0 || y+dy[k] >= board.size() )
                            continue;
                        if (flag[x+dx[k]][y+dy[k]]) continue;
                        if (board[x+dx[k]][y+dy[k]] == 'O') {
                            flag[x+dx[k]][y+dy[k]] = true;
                            s.insert(make_pair(x+dx[k], y+dy[k]));
                            q.push(x+dx[k]);
                            q.push(y+dy[k]);
                            if (!is_fill || x+dx[k] == 0 || x+dx[k] == board.size()-1 ||
                                    y+dy[k] == 0 || y+dy[k] == board.size() - 1)
                                is_fill = false;
                        }
                    }
                }
                
                 if (is_fill) {
                    for (auto it = s.begin(); it != s.end(); ++it) {
                        board[it->first][it->second] = xxx;
                    }
                 }
            }
        }
    }
}

};

 

脑残，又写一遍。

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.size() ==0 ) return;
        vector<vector<bool> > m(board.size());
        for (int i = 0; i < board.size(); ++i) {
            m[i].resize(board[i].size());
            fill(m[i].begin(), m[i].end(), 0);
        }
        
        for (int i = 0; i < board.size(); ++i) {
            floodfill(i, 0, board, m);
            floodfill(i, board[i].size()-1, board, m);
        }
        for (int i = 0; i < board[0].size(); ++i) {
            floodfill(0, i, board, m);
            floodfill(board.size()-1, i, board, m);
        }
        
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                if (board[i][j] == 'O' && m[i][j] == false)
                  board[i][j] = 'X';
            }
        }
    }
    
    void floodfill(int r, int c, const vector<vector<char>>& board, vector<vector<bool>>& m) {
        if (board[r][c] == 'X' || m[r][c] == true) return;
        queue<pair<int,int> > q;
        int x,y, x2, y2;
        const int dx[] = {0, 0, 1, -1};
        const int dy[] = {1, -1, 0, 0};
        q.push(make_pair(r,c));
        m[r][c] = true;
        while (!q.empty()) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                x2 = x + dx[i];
                y2 = y + dy[i];
                if (inrange(x2, y2, board) && board[x2][y2] == 'O' && m[x2][y2] == false) {
                    m[x2][y2] = true;
                    q.push(make_pair(x2, y2));
                }
            }
        }
    }
    bool inrange(int i, int j, const vector<vector<char>>& b) {
        return i >=0 && j >= 0 && i < b.size() && j < b[0].size();
    }
};

 

 

class Solution {
public:
    int n, m;
    vector<vector<bool> > v;
    void solve(vector<vector<char>> &board) {
        auto &a = board;
        n = a.size();
        if (n == 0) return;
        m = a[0].size();
        v.clear();
        for (int i = 0; i < n; i++) {
            v.push_back(vector<bool>(m, 0));
        }
        
        //floodfill
        queue<int> x, y;
        for (int i = 0; i < m; i++) {
            if (a[0][i] == 'O') x.push(0), y.push(i);
            if (a[n-1][i] == 'O') x.push(n-1), y.push(i);
        }
        for (int i = 1; i < n-1; i++) {
            if (a[i][0] == 'O') x.push(i), y.push(0);
            if (a[i][m-1] == 'O') x.push(i), y.push(m-1);
        }
        int dx[] = {-1, 1, 0, 0};
        int dy[] = {0, 0, -1, 1};
        while (!x.empty()) {
            int curx = x.front(); x.pop();
            int cury = y.front(); y.pop();
            if (v[curx][cury] == true || a[curx][cury] != 'O') continue;
            v[curx][cury] = true;
            a[curx][cury] = '.';
            
            for (int i = 0; i < 4; i++) {
                if (isOK(curx+dx[i], cury+dy[i]) && a[curx+dx[i]][cury+dy[i]] == 'O') {
                    x.push(curx+dx[i]);
                    y.push(cury+dy[i]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == '.') a[i][j] = 'O';
                else if (a[i][j] == 'O') a[i][j] = 'X';
            }
        }
    }
    
    bool isOK(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m && v[x][y] == false;
    }

};