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. // LeetCode, Surrounded Regions
  2. // BFS，时间复杂度O(n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     void solve(vector<vector<char>> &board) {
  6.         if (board.empty()) return;
  8.         const int m = board.size();
  9.         const int n = board[0].size();
  10.         for (int i = 0; i < n; i++) {
  11.             bfs(board, 0, i);
  12.             bfs(board, m - 1, i);
  13.         }
  14.         for (int j = 1; j < m - 1; j++) {
  15.             bfs(board, j, 0);
  16.             bfs(board, j, n - 1);
  17.         }
  18.         for (int i = 0; i < m; i++)
  19.             for (int j = 0; j < n; j++)
  20.                 if (board[i][j] == 'O')
  21.                     board[i][j] = 'X';
  22.                 else if (board[i][j] == '+')
  23.                     board[i][j] = 'O';
  24.     }
  25. private:
  26.     void bfs(vector<vector<char>> &board, int i, int j) {
  27.         typedef pair<int, int> state_t;
  28.         queue<state_t> q;
  29.         const int m = board.size();
  30.         const int n = board[0].size();
  32.         auto state_is_valid = [&](const state_t &s) {
  33.             const int x = s.first;
  34.             const int y = s.second;
  35.             if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
  36.                 return false;
  37.             return true;
  38.         };
  40.         auto state_extend = [&](const state_t &s) {
  41.             vector<state_t> result;
  42.             const int x = s.first;
  43.             const int y = s.second;
  44.             // 上下左右
  45.             const state_t new_states[4] = {{x-1,y}, {x+1,y},
  46.                     {x,y-1}, {x,y+1}};
  47.             for (int k = 0; k < 4;  ++k) {
  48.                 if (state_is_valid(new_states[k])) {
  49.                     // 既有标记功能又有去重功能
  50.                     board[new_states[k].first][new_states[k].second] = '+';
  51.                     result.push_back(new_states[k]);
  52.                 }
  53.             }
  55.             return result;
  56.         };
  58.         state_t start = { i, j };
  59.         if (state_is_valid(start)) {
  60.             board[i][j] = '+';
  61.             q.push(start);
  62.         }
  63.         while (!q.empty()) {
  64.             auto cur = q.front();
  65.             q.pop();
  66.             auto new_states = state_extend(cur);
  67.             for (auto s : new_states) q.push(s);
  68.         }
  69.     }
  70. };

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