c++ - BFS Surrounding -
given nxn grid of 0s, 1s, , 2s, find out whether 1s or 2s surrounded. being surrounded means 1s surrounded 2s or 2s surrounded 1s.
010 121 010
means 2 surround one. there complicated like:
10110 21212 11111
the 2 surround 1 because (2,1) surround 1 , (0,1) not surround 1 because no 1 in left of (0,1).
how determine contains , how solve problem.
assume table a
size m*n. should add boundary around table (like following picture)
you can that:
- assume check position
(i,j)
of table surrounded or not? - bfs
(i,j)
condition(a[u][v] == a[i][j] || a[u][v] == 0)
-> add(u,v)
stack - if visit boundary (
a[0][x]
,a[x][0]
,a[m+1][x]
,a[x][n+1]
) -> not surrounded
Comments
Post a Comment