转载

surrounded-regions

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

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

思想

题目看了老半天………..

对四个边界DFS, 找到与其相连的‘O’, 找到后将其变为其他字符作为访问标记

这样可以节省空间,使得内存不会超限

还有记住 dfs的时候, 能用引用就用引用否则会超时

代码

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size() == 0) return;
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if ((i == 0 || i == board.size() - 1 || j == 0 || j == board[i].size() - 1) && board[i][j] == 'O')
                    dfs(i, j, board);
            }
        }
         for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }

   void dfs(int x, int y, vector<vector<char> > &board) {
        board[x][y] = '$';
        if(x-1 >= 0 && board[x-1][y] == 'O' ) {
            dfs(x-1, y, board);
        }
        if(x+1 < board.size() && board[x+1][y] == 'O' ) {
            dfs(x+1, y, board);
        }
        if(y-1 >= 0 && board[x][y-1] == 'O' ) {
            dfs(x, y-1, board);
        }
        if(y+1 < board[x].size() && board[x][y+1] == 'O' ) {
            dfs(x, y+1, board);
        }
    }
};
正文到此结束
本文目录