Careercup

2014-05-06 14:04

原题：

given an 2D matrix M, is filled either using X or O, you need to find the region which is filled by O and surrounded by X 
and fill it with X. 

example 1: 

X X X X X 
X X O O X 
X X O O X 
O X X X X 

Answer : 

X X X X X 
X X X X X 
X X X X X 
O X X X X 

example 2: 

X X X X X 
X X O O X 
X X O O O 
O X X X X 

answer 2: 
X X X X X 
X X O O X 
X X O O O 
O X X X X

题目：参见Leetcode题目Surrounded Regions。

解法：题解位于LeetCode - Surrounded Regions。

代码：

  1 // http://www.careercup.com/question?id=5727310284062720
  2 #include <iostream>
  3 #include <queue>
  4 #include <string>
  5 #include <vector>
  6 using namespace std;
  7 
  8 class Solution {
  9 public:
 10     void solve(vector<vector<char> > &board) {
 11         // Should n or m be smaller than 3, there'll be no captured region.
 12         n = (int)board.size();
 13         if (n < 3) {
 14             return;
 15         }
 16         
 17         m = (int)board[0].size();
 18         if (m < 3) {
 19             return;
 20         }
 21         
 22         int i, j;
 23         
 24         // if an 'O' is on the border, all of its connected 'O's are not captured.
 25         // so we scan the border and mark those 'O's as free.
 26         
 27         // the top row
 28         for (j = 0; j < m; ++j) {
 29             if (board[0][j] == 'O') {
 30                 check_region(board, 0, j);
 31             }
 32         }
 33         
 34         // the bottom row
 35         for (j = 0; j < m; ++j) {
 36             if (board[n - 1][j] == 'O') {
 37                 check_region(board, n - 1, j);
 38             }
 39         }
 40         
 41         // the left column
 42         for (i = 1; i < n - 1; ++i) {
 43             if (board[i][0] == 'O') {
 44                 check_region(board, i, 0);
 45             }
 46         }
 47         
 48         // the right column
 49         for (i = 1; i < n - 1; ++i) {
 50             if (board[i][m - 1] == 'O') {
 51                 check_region(board, i, m - 1);
 52             }
 53         }
 54         
 55         // other unchecked 'O's are all captured
 56         for (i = 0; i < n; ++i) {
 57             for (j = 0; j < m; ++j) {
 58                 if (board[i][j] == '#') {
 59                     // free 'O's
 60                     board[i][j] = 'O';
 61                 } else if (board[i][j] == 'O') {
 62                     // captured 'O's
 63                     board[i][j] = 'X';
 64                 }
 65             }
 66         }
 67     }
 68 private:
 69     int n, m;
 70     
 71     void check_region(vector<vector<char> > &board, int startx, int starty) {
 72         if (startx < 0 || startx > n - 1 || starty < 0 || starty > m - 1) {
 73             return;
 74         }
 75         if (board[startx][starty] == 'O') {
 76             board[startx][starty] = '#';
 77             check_region(board, startx - 1, starty);
 78             check_region(board, startx + 1, starty);
 79             check_region(board, startx, starty - 1);
 80             check_region(board, startx, starty + 1);
 81         }
 82     }
 83 };
 84 
 85 int main()
 86 {
 87     int n, m;
 88     int i, j;
 89     string str;
 90     vector<vector<char> > board;
 91     Solution sol;
 92     
 93     while (cin >> n >> m && (n > 0 && m > 0)) {
 94         board.resize(n);
 95         for (i = 0; i < n; ++i) {
 96             cin >> str;
 97             board[i].resize(m);
 98             for (j = 0; j < m; ++j) {
 99                 board[i][j] = str[j];
100             }
101         }
102         sol.solve(board);
103         for (i = 0; i < n; ++i) {
104             for (j = 0; j < m; ++j) {
105                 cout << board[i][j];
106             }
107             cout << endl;
108         }
109         
110         for (i = 0; i < n; ++i) {
111             board[i].clear();
112         }
113         board.clear();
114     }
115     
116     return 0;
117 }