Surrounded Regions--LeetCode

Dear 丶 2022-08-07 13:38 8阅读 0赞

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.

例如：

输入：

X X X X

X O O X

X X O X

X O X X

输出：

X X X X

X O X X

分析：

典型的BFS题目。遍历每个字符，如果是“O”，则从当前字符开始BFS遍历，如果周围也是“O”则加入当前遍历的队列，知道遍历完所有相邻的“O”，于此同时，判断每个O是否是被包围的，只有由一个O是没有被包围的，则当前遍历的O的集合都是没有被包围的，因为这些O都是相连的。

对于BFS不是很熟悉，这里看一个例子熟悉一下。

public class Solution {
    public static void solve(char[][] board) {
        Queue<Integer> queue = new LinkedList<Integer>();
        if (board == null || board.length == 0)
          return;
        int m = board.length;
        int n = board[0].length;
        boolean visited[][] = new boolean[m][n];
        int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
    
            //以下是标准的BFS搜索，用visitedPoints记录访问的O
            if (board[i][j] == 'O' && !visited[i][j]) {
              boolean surounned = true;
              List<Integer> visitedPoints = new ArrayList<Integer>();
              queue.add(i * n + j);
              visited[i][j] = true;
              while (queue.size() > 0) {
                int point = queue.poll();
                visitedPoints.add(point);
                int x = point/n;
                int y = point%n;
                for (int k = 0; k < 4; k++) {
                  int nextx = x + dir[k][0];
                  int nexty = y + dir[k][1];
                  if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
                    if (board[nextx][nexty] == 'O' && !visited[nextx][nexty])
                      queue.add(nextx * n + nexty);
                    visited[nextx][nexty] = true;
                  } else {
                    surounned = false;
                  }
                }
              }
    
              //如果当前遍历到的O是被包围的
              if (surounned) {
                for (int p : visitedPoints)
                  board[p / n][p % n] = 'X';
              }
            }
          }
        }
      }
    }