本文共 3293 字，大约阅读时间需要 10 分钟。

https://oj.leetcode.com/problems/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 XX O O XX X O XX O X X

After running your function, the board should be:

X X X XX X X XX X X XX O X X

这样的题目要得到一个答案，其实DFS和BFS都是可行的，理论上也不存在实际performance上的差距。本质的做法就是对每一片联通的0区域，做一次DFS或者BFS遍历其有效性并且改变其值。为了对联通区域只做一次遍历，标记是必须的。而不管是BFS还是DFS标记的方式一般来说是用HashMap或者HashSet记录路径，但是这一题的特质表示它其实可以in-place。把遍历过的O直接变成X（成功的情况）或者T（不成功的情况）即可，这样就标记了。最后把标记为T的改回O就好。这样就能inplace了。

这一题leetcode的online judge对performance要求有点奇怪，虽然算法角度上，DFS的实际performance不会比BFS差（甚至更高，DFS递归只需要每个元素access不超过两次）。但事实上oj上放了一个很极端的case会让DFS出现stackoverflow的exception，也就是递归层级爆掉了。所以下面先放BFS的代码：

    public void solve(char[][] board) {         if(board.length == 0 || board[0].length == 0)             return;         for(int i = 1; i < board.length - 1; i++){             for(int j = 1; j < board[0].length - 1; j++){                 if(board[i][j] == 'O')helper(board, i, j);             }         }         for(int i = 0; i < board.length; i++)             for(int j = 0; j < board[0].length; j++)                 board[i][j] = board[i][j] == 'T' ? 'O' : board[i][j];     }          public void helper(char[][] board, int i, int j){         boolean isValid = true;         Queue
   
     queue = new LinkedList
    
     ();         LinkedList
     
       res_candidate = new LinkedList
      
       ();         queue.add(new Point(i, j));         while(!queue.isEmpty()){             Point p = queue.poll();             int x = p.x;             int y = p.y;             if(board[x][y] == 'T' || board[x][y] == 'X')                 continue;             if(x == 0 || y == 0 || x == board.length - 1 || y == board[0].length - 1){                 isValid = false;                 continue;             }             board[x][y] = 'T';             res_candidate.add(p);             queue.add(new Point(x - 1, y));             queue.add(new Point(x + 1, y));             queue.add(new Point(x, y - 1));             queue.add(new Point(x, y + 1));         }         if(isValid){             for(Point p : res_candidate)                 board[p.x][p.y] = 'X';         }     }
      
     
    
   

public void solve(char[][] board) {        if(board.length == 0 || board[0].length == 0)            return;        for(int i = 1; i < board.length - 1; i++){            for(int j = 1; j < board[0].length - 1; j++){                if(board[i][j] == 'O' && helper(board, i, j));            }        }        for(int i = 0; i < board.length; i++)            for(int j = 0; j < board[0].length; j++)                board[i][j] = board[i][j] == 'T' ? 'O' : board[i][j];    }        public boolean helper(char[][] board, int i, int j){        if(board[i][j] == 'X' || board[i][j] == 'T')            return true;        if(i == 0 || i == board.length - 1 || j == 0 || j == board[0].length - 1)            return false;        board[i][j] = 'T';        if(helper(board, i - 1, j) && helper(board, i + 1, j) && helper(board, i, j - 1) && helper(board, i, j + 1)){            board[i][j] = 'X';            return true;        }else            return false;    }

转载地址：http://mgaxb.baihongyu.com/