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,

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

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
C++:
01 void change(vector<vector<char>> &board, queue<int>& x, queue<int>& y)
02 {
03     int n=board.size();
04     int m=board[0].size();
05     while(!x.empty())
06     {
07         int p=x.front();
08         x.pop();
09         int q=y.front();
10         y.pop();
11         board[p][q]=‘Y’;
12         if((p>0)&&(board[p1][q]==‘O’))
13         {
14             x.push(p1);
15             y.push(q);
16         }
17         if((p<n1)&&(board[p+1][q]==‘O’))
18         {
19             x.push(p+1);
20             y.push(q);
21         }
22         if((q>0)&&(board[p][q1]==‘O’))
23         {
24             x.push(p);
25             y.push(q1);
26         }
27         if((q<m1)&&(board[p][q+1]==‘O’))
28         {
29             x.push(p);
30             y.push(q+1);
31         }
32     }
33 }
34 class Solution {
35 public:
36     void solve(vector<vector<char>> &board) {
37         // Start typing your C/C++ solution below
38         // DO NOT write int main() function
39         int n=board.size();
40         if(n<=2)
41             return;
42         int m=board[0].size();
43         if(m<=2)
44             return;
45         queue<int> x;
46         queue<int> y;
47         for(int i=0;i<n;i++)
48         {
49             if(board[i][0]==‘O’)
50             {
51                 x.push(i);
52                 y.push(0);
53             }
54             if(board[i][m1]==‘O’)
55             {
56                 x.push(i);
57                 y.push(m1);
58             }
59         }
60         for(int i=0;i<m;i++)
61         {
62             if(board[0][i]==‘O’)
63             {
64                 x.push(0);
65                 y.push(i);
66             }
67             if(board[n1][i]==‘O’)
68             {
69                 x.push(n1);
70                 y.push(i);
71             }
72         }
73         change(board,x,y);
74         for(int i=0;i<n;i++)
75         {
76             for(int j=0;j<m;j++)
77             {
78                 if(board[i][j]==‘Y’)
79                     board[i][j]=‘O’;
80                 else
81                     board[i][j]=‘X’;
82             }
83         }
84     }
85 };
Advertisements
This entry was posted in Graph, Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s