Identify Groups on a Board - Step 1

◀ Exercise #1: Identify Groups on a Board▶ Identify Groups on a Board - Step 2 Amazon Let’s think about the overall design of the program by running the 1st step of the Four-Step Programming Model!

Four Step Programming Model: Step 1
First we declare a bool array of size specified by the user and initialize each element to false, indicating that no spots are occupied. Then we read in the locations of the people, making the corresponding elements in the array true.

Now here comes the heart of the program: find all groups. One way to do it is to use recursion. For each occupied square, examine its surrounding squares recursively. After determining and listing all groups, we are done. As you can see, we do not really need to use a class; the recursive function can be written as a nonmember function. Here is my skeleton:

void process(int, int);

int main(int argc, char **argv){
- if arguments are not correct, give an error message and quit
- receive locations of people in the given file and assign proper values to all squares on the grid
- go through each square on the grid, find the groups, and store them into a vector 
- output results to the output file, specified by the command line
}

/*
precondition: x and y can never go out of the grid’s bounds
postcondition: tempvx and tempvy will contain people belonging to a group
*/
void process(int x, int y) {
- mark square (x, y) handled
- store them in two vectors, tempvx and tempvy
- if the east square is occupied and not handled yet, call process on that square
- if the west square is occupied and not handled yet, call process on that square
- if the north square is occupied and not handled yet, call process on that square
- if the south square is occupied and not handled yet, call process on that square
}

You can, of course, find the groups without using a recursion. For example, scan the board and if a particular square is occupied, see if it belongs to any of the groups stored previously. If so, store it as belonging to that group. If not, store it as a new group. This algorithm works but it is not as cool as the recursive version, is it?

Next let's look at the next step!◀ Exercise #1: Identify Groups on a Board▶ Identify Groups on a Board - Step 2