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
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
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,
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
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.
// 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