-
problem!!
Hello,I have an assignment question and I cant understand it properly.Can anyone of you help me?Here is the question...
An N x N square consists of black and white cells arranged in a certain way. The problem
is to determine the number of white areas and the number of white cells in each area. For
example a regular 8 x 8 chess board has 32 one-cell white areas, similarly consider the
following two 5 x 5 boards have 3 and 4 white areas respectively each of size 4 white
cells.
b b w w b
b b w w b
b b b b b
w w b w w
w w b w w
w w b w w
w w b w w
b b b b b
w w b w w
w w b w w
Write a program that, for a give N x N square(Array), outputs the number of white areas
and their sizes. Use an N+2 x N+2 array with properly marked cells. Two additional rows
and columns constitute a frame of black cells surrounding the entered square to simplify
your implementation. For example the given left hand side (LHS) square is store in the
right hand side (RHS) array:
(LHS)
b b w w b
b b w w b
b b b b b
w w b w w
w w b w w
(RHS)
b b b b b b b
b w w b w w b
b w w b w w b
b b b b b b b
b w w b w w b
b w w b w w b
b b b b b b b
Hint: Traverse the square row by row and, for the first unvisited cell encountered invoke
a function call that process one area. The secret is in using four recursive calls in this
function for each unvisited white cell and marking it with a special symbol as visited
(counted).
Is there any nested loops neede to traverse row by row,or the backtracking will solve it?
-
?
Code:
for (int y = 0; y != height; ++y) {
for (int x = 0; x != width; ++x) {
if (array[y][x] == 'w')
//...
I think the idea is that you are allowed to modify the contents of the array (at the end white squares are all marked as counted), or you can loop over the array again and set counted squares back to 'w' at the end.
-
The secret reffered to is a basic flood fill. Check Wikipedia.
You need to iterate through every cell, and attempt to do a flood-fill for white. If it's successful, you add to a numberOfAreas counter . You can make the flood fill method return a count of how many were filled, so you can say sizeOfArea=fill(x,y)
-
