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,

  1. X X X X
  2. X O O X
  3. X X O X
  4. X O X X

After running your function, the board should be:

  1. X X X X
  2. X X X X
  3. X X X X
  4. X O X X

分析

广搜。从上下左右四个边界往里走，凡是能碰到的'O'，都是跟边界接壤的，应该保留。

代码

  1. // Surrounded Regions
  2. // BFS，时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public void solve(char[][] board) {
  5.         if (board.length == 0) return;
  7.         final int m = board.length;
  8.         final int n = board[0].length;
  9.         for (int i = 0; i < n; i++) {
  10.             bfs(board, 0, i);
  11.             bfs(board, m - 1, i);
  12.         }
  13.         for (int j = 1; j < m - 1; j++) {
  14.             bfs(board, j, 0);
  15.             bfs(board, j, n - 1);
  16.         }
  17.         for (int i = 0; i < m; i++)
  18.             for (int j = 0; j < n; j++)
  19.                 if (board[i][j] == 'O')
  20.                     board[i][j] = 'X';
  21.                 else if (board[i][j] == '+')
  22.                     board[i][j] = 'O';
  23.     }
  24.     private static void bfs(char[][] board, int i, int j) {
  25.         Queue<State> q = new LinkedList<>();
  26.         final int m = board.length;
  27.         final int n = board[0].length;
  29.         final Function<State, Boolean> stateIsValid = (State s) -> {
  30.             if (s.x < 0 || s.x >= m || s.y < 0 || s.y >= n ||
  31.                     board[s.x][s.y] != 'O')
  32.                 return false;
  33.             return true;
  34.         };
  35.         final Function<State, ArrayList<State>> stateExtend = (State s) -> {
  36.             ArrayList<State> result = new ArrayList<>();
  37.             final int x = s.x;
  38.             final int y = s.y;
  39.             // 上下左右
  40.             State[] newStates = new State[]{new State(x-1, y),
  41.                     new State(x+1,y),
  42.                     new State(x,y-1),
  43.                     new State(x,y+1)
  44.             };
  45.             for (int k = 0; k < 4; ++k) {
  46.                 if (stateIsValid.apply(newStates[k])) {
  47.                     // 既有标记功能又有去重功能
  48.                     board[newStates[k].x][newStates[k].y] = '+';
  49.                     result.add(newStates[k]);
  50.                 }
  51.             }
  52.             return result;
  53.         };
  54.         State start = new State(i, j);
  55.         if (stateIsValid.apply(start)) {
  56.             board[i][j] = '+';
  57.             q.offer(start);
  58.         }
  59.         while (!q.isEmpty()) {
  60.             State cur = q.poll();
  61.             ArrayList<State> newStates = stateExtend.apply(cur);
  62.             for (State s : newStates) q.offer(s);
  63.         }
  64.     }
  65.     static class State {
  66.         private int x;
  67.         private int y;
  68.         public State(int x, int y) {
  69.             this.x = x;
  70.             this.y = y;
  71.         }
  72.     }
  73. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/bfs/surrounded-regions.html