Surrounded Regions [未完成]

思路完全一样

AC的代码：

 1 class Solution {
 2     private:
 3         struct Point {
 4             int x, y;
 5             Point(int _x, int _y):x(_x), y(_y) {}
 6         };
 7     public:
 8         void solve(vector<vector<char> > & board) {
 9             const int M = board.size();
10             if (M <= 2) return;
11             const int N = board[0].size();
12             vector<Point> run; // 没被包含的O，判断后修改为D来标记
13             for (int i=0; i<M; ++i)     // 1 边界
14                 for (int j=0; j<N; ++j) 
15                     if ((i==0 || i==M-1 || j==0 || j==N-1) && board[i][j]=='O') { 
16                         board[i][j] = 'D';
17                         run.push_back(Point(i, j));
18                     }
19 
20             const static int PATH[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
21             while (!run.empty()) {      // 2 out -> insider
22                 Point p = run.back();
23                 run.pop_back();
24                 for (int i=0; i<4; ++i) {
25                     int x = p.x+PATH[i][1];
26                     int y = p.y+PATH[i][0];
27                     if (x<0 || x>=M || y<0 || y>= N || board[x][y]!='O')
28                         continue;
29                     board[x][y] = 'D';
30                     run.push_back(Point(x, y));
31                 }
32             }
33 
34             for (int i=0; i<M; ++i)     // 3 检查
35                 for (int j=0; j<N; ++j) {
36                     if (board[i][j]=='X') continue;
37                     board[i][j] = (board[i][j]=='O'?'X':'O');
38                 }
39         }
40 };

时间通不过的代码：

 1 class Solution {
 2 public:
 3     void solve(vector<vector<char>> &board) {
 4         int size = board.size();
 5         if (size < 3)
 6             return;
 7   
 8         for (int j = 0; j < size; ++j) {
 9             if (board[0][j] == 'O') {
10                 board[0][j] == '1';
11                 judgeRegion(board, 1, j);
12             }
13             
14             if (board[size-1][j] == 'O') {
15                 board[size-1][j] == '1';
16                 judgeRegion(board, size-2, j);
17             }
18         }
19         
20         for (int i = 1; i < size - 1; ++i) {
21             if (board[i][0] == 'O') {
22                 board[i][0] == '1';
23                 judgeRegion(board, i, 1);
24             }
25             
26             if (board[i][size-1] == 'O') {
27                 board[i][size-1] == '1';
28                 judgeRegion(board, i, size - 2);
29             }            
30         }
31 
32         for (int i = 0; i < size; ++i) {
33             for (int j = 0; j < size; ++j) {
34                 if (board[i][j] == 'O')
35                     board[i][j] = 'X';
36                 if (board[i][j] == '1')
37                     board[i][j] == 'O';
38             }
39         }
40     }
41     
42     void judgeRegion(vector<vector<char>> &board, int i, int j) {
43         int size = board.size();
44         if (i >= 0 && j < size && board[i][j] == 'O') {
45             board[i][j] == '1';
46             judgeRegion(board, i-1, j);
47             judgeRegion(board, i+1, j);
48             judgeRegion(board, i, j-1);
49             judgeRegion(board, i, j+1);
50         }
51     }
52 
53 };