[algogeeks] Re: Intrestting problem
pick '0' and keep track if we have visited that '0' before a '0' will not surrender if it is on boundary a '0' is ready to surrender if 1. it is surrounded by no '0' in all 4 directions (easy one) or 2. if it is surrounded by 1 to 4 '0' then it will surrender but we will ask each of the neighbouring '0' . so in this case traverse all neighbouring '0' and ask each one if it is ready to surrender. if all say yes then surrender them all . if even one of them says no, then whole group should not surrender -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Intrestting problem
Start dfs from the boundary of matrix from each element which is a zero(mark it to Z), and mark all reachable zeroes as D. Finally traverse the matrix marking all as X except the D's, mark them as O. eg: xxox xoxx xxox the inner o's would be marked as D's since we can get to the from the o in the last line that is at a boundary and thus guarantees an opening. On Tuesday, June 11, 2013 12:35:30 PM UTC+5:30, Jai Shri Ram wrote: 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 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Intrestting problem
juat want to ask why the last region was not flipped from o to x?
On Tue, Jun 11, 2013 at 11:57 PM, Don dondod...@gmail.com wrote:
// Flip a region including location (x,y) from from to to.
// Returns true if region is surrounded.
bool flip(char board[][], int n, int x, int y, char from, char to)
{
if ((x = 0) (y = 0) (x n) (y n)) return false;
if (board[x][y] != from) return true;
board[x][y] = to;
return flip(board,n,x-1,y) flip(board,n,x+1,y)
flip(board,n,x,y-1) flip(board,n,x,y+1);
}
// Flips all regions of 'O' completely surrounded by 'X' to 'X'
void captureSurrounded(char board[][], int n, int x, int y)
{
int x,y;
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (flip(board,n,x,y,'O','v'))
flip(board,n,x,y, 'v', 'X');
// Set regions not surrounded back to 'O'
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (board[x][y] == 'v') board[x][y] = 'O';
}
On Jun 11, 3:05 am, Jai Shri Ram del7...@gmail.com wrote:
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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Intrestting problem
It touches an edge of the region, and is therefore not surrounded.
On Jun 12, 2:39 am, Nishant Pandey nishant.bits.me...@gmail.com
wrote:
juat want to ask why the last region was not flipped from o to x?
On Tue, Jun 11, 2013 at 11:57 PM, Don dondod...@gmail.com wrote:
// Flip a region including location (x,y) from from to to.
// Returns true if region is surrounded.
bool flip(char board[][], int n, int x, int y, char from, char to)
{
if ((x = 0) (y = 0) (x n) (y n)) return false;
if (board[x][y] != from) return true;
board[x][y] = to;
return flip(board,n,x-1,y) flip(board,n,x+1,y)
flip(board,n,x,y-1) flip(board,n,x,y+1);
}
// Flips all regions of 'O' completely surrounded by 'X' to 'X'
void captureSurrounded(char board[][], int n, int x, int y)
{
int x,y;
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (flip(board,n,x,y,'O','v'))
flip(board,n,x,y, 'v', 'X');
// Set regions not surrounded back to 'O'
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (board[x][y] == 'v') board[x][y] = 'O';
}
On Jun 11, 3:05 am, Jai Shri Ram del7...@gmail.com wrote:
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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Intrestting problem
How about the following: 1. Think every cell on a board occupied by an O is a vertex in a non-directed graph. Add a special vertex called OuterWorld. 2. Connect all neighboring vertices with edges, based on how you define surrounded by X-es. E.g. in your picture, diagonals are not allowed. 3. Connect all vertices on the board's boundaries to the OuterWorld vertex. Now, you should split your graph into connected subgraphs (use DFS or BFS - both will work). You will get at most one subgraph containing the OuterWorld vertex (which you don't touch) plus zero or more subgraphs of surrounded O-vertices (where you flip all vertices from O to X. An alternative approach would be to represent O-regions using Disjoint Sets to and use Find-And-Union algorithm to solve it. Thanks! On Tuesday, June 11, 2013 3:05:30 AM UTC-4, Jai Shri Ram wrote: 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 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Intrestting problem
// Flip a region including location (x,y) from from to to.
// Returns true if region is surrounded.
bool flip(char board[][], int n, int x, int y, char from, char to)
{
if ((x = 0) (y = 0) (x n) (y n)) return false;
if (board[x][y] != from) return true;
board[x][y] = to;
return flip(board,n,x-1,y) flip(board,n,x+1,y)
flip(board,n,x,y-1) flip(board,n,x,y+1);
}
// Flips all regions of 'O' completely surrounded by 'X' to 'X'
void captureSurrounded(char board[][], int n, int x, int y)
{
int x,y;
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (flip(board,n,x,y,'O','v'))
flip(board,n,x,y, 'v', 'X');
// Set regions not surrounded back to 'O'
for(x = 0; x n; ++x)
for(y = 0; y n; ++y)
if (board[x][y] == 'v') board[x][y] = 'O';
}
On Jun 11, 3:05 am, Jai Shri Ram del7...@gmail.com wrote:
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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
