surrounded regions

surrounded regions

Search

The problm ask us to put all 'O'(big orange not zero) to 'X' if the region of 'O's is durrounded by 'X' in all four directions. Those regions would not be changed to 'X' must connect to on edge of the matrix. So search each edge and if it is 'O' then mark those points connect to this with DFS or BFS. Then change the rest 'O' to 'X', change the marked region to 'O'.

 1 class Solution {
 2 private:
 3     int visited[1000][1000];
 4     int deltaX[4] = {-1,1,0,0};
 5     int deltaY[4] = {0,0,-1,1};
 6     int n;
 7     int m;
 8 public:
 9     void solve(vector<vector<char>> &board) {
10         memset(visited,0,sizeof(visited));
11         n = board.size();
12         if ( !n ) {
13             return;
14         }
15         m = board[0].size();
16         if ( !m ) {
17             return;
18         }
19         queue< pair<int, int> > Q; 
20         while ( !Q.empty() ) {
21             Q.pop();
22         }
23         for ( int i = 0; i < n; i++ ) {
24             if ( 'O' == board[i][0] ) {
25                 visited[i][0] = 1;
26                 pair < int , int > p(i,0);
27                 Q.push(p);
28             }
29             if ( 'O' == board[i][m-1] ) {
30                 visited[i][m-1] = 1;
31                 pair < int , int > p(i,m-1);
32                 Q.push(p);
33             }
34         }
35         for ( int i = 0; i < m; i++ ) {
36             if ( 'O' == board[0][i] ) {
37                 visited[0][i] = 1;
38                 pair < int , int > p(0,i);
39                 Q.push(p);
40             }
41             if ( 'O' == board[n-1][i] ) {
42                 visited[n-1][i] = 1;
43                 pair < int , int > p(n-1,i);
44                 Q.push(p);
45             }
46         }
47         while( !Q.empty() ) {
48             auto t = Q.front();
49             Q.pop();
50             int x = t.first;
51             int y = t.second;
52             board[x][y] = '*';
53             for ( int i = 0; i < 4; i++ ) {
54                 int newX = x + deltaX[i];
55                 int newY = y + deltaY[i];
56                 pair< int, int > p(newX,newY);
57                 if ( isVisitable(newX,newY,board) ) {
58                     visited[newX][newY] = 1;
59                     Q.push(p);
60                 }
61             }
62         }
63         for ( int i = 0; i < n; i++ ) {
64             for ( int j = 0; j < m; j++ ) {
65                 if ( 'O' == board[i][j] ) {
66                     board[i][j] = 'X';
67                 }
68                 if ( '*' == board[i][j] ) {
69                     board[i][j] = 'O';
70                 }
71             }
72         }
73     }
74     bool isVisitable( int x, int y, vector< vector <char> >& board ) {
75         if ( x < 0 || x >= n ) {
76             return false;
77         }
78         if ( y < 0 || y >= m ) {
79             return false;
80         }
81         if ( 'O' != board[x][y] ) {
82             return false;
83         }
84         if ( 1 == visited[x][y] ) {
85             return false;
86         }
87         return true;
88     }
89 };

Mistakes

  • 'O' is not '0'.
  • When need to take matrix as argument, use &.

Loading Disqus comments...
Table of Contents