Identify Groups on a Board - Step 4

◀ Identify Groups on a Board - Step 3▶ Exercise #2: The Game of Nim
Amazon Let’s run the last step of the Four-Step Programming Model!

Four Step Programming Model: Step 4
The program is rather straightforward and easy to code. The following is the complete program.
/*
Michael Wen
6/6/2003
Given the size of the grid and the layout of people, this program outputs relevant information about each group on the grid.
*/
#include<iostream>
#include<fstream>
#include<vector> using namespace std; int width, height, total; vector<int> tempvx, tempvy; bool **occupy, **handled; void process(int, int); int main(int argc, char **argv){ /* if arguments are not correct, give an error message and quit */ if(argc!=3){ cout<<"usage: ./exe <inputFile> <outputFile>\n"; cout<<"<inputFile>: input file's name\n"; cout<<"<outputFile>: output file's name\n";
exit(1); } int i,j; char *fileIn, *fileOut; ifstream fin; ofstream fout; vector<vector<int> > groupX, groupY; /* receive locations of people in the given file and assign proper values to all squares on the grid */ fileIn=argv[1]; fileOut=argv[2]; fin.open(fileIn); fin>>width; fin>>height; occupy = new bool*[width]; handled = new bool*[width]; for(i=0;i<width;i++){ occupy[i] = new bool[height];
handled[i] = new bool[height]; } for(i=0;i<width;i++) for(j=0;j<height;j++) handled[i][j]=occupy[i][j]=false; while(fin) { fin>>i; fin>>j; if(i<0 || i>=width || j<0 || j>=height) continue; occupy[i][j]=true; } fin.close(); /* go through each square on the grid, find the groups, and store them into a vector */ for(i=0;i<width;i++) for(j=0;j<height;j++)
if(occupy[i][j] && !handled[i][j]){ process(i,j); groupX.push_back(tempvx); groupY.push_back(tempvy); tempvx.clear(); tempvy.clear(); } total=groupX.size(); /* output results to the output file, specified by the command line */ fout.open(fileOut); fout<<"There are a total of "<<total<<" group(s).\n\n"; for(i=0;i<total;i++){ tempvx=groupX[i]; tempvy=groupY[i]; fout<<"Group "<<i+1<<": "<<tempvx.size()<<" person(s).\n";
for(j=0;j<tempvx.size();j++) fout<<"\t"<<tempvx[j]<<' '<<tempvy[j]<<endl; fout<<endl; } fout.close(); return 0; } /* precondition: x and y can never go out of the board’s bounds postcondition: tempvx and tempvy will contain people belonging to a group */ void process(int x, int y) { /* mark square (x, y) handled */ handled[x][y]=true; /* store it in a vector */ tempvx.push_back(x);
tempvy.push_back(y); /* if the east square is occupied and not handled, call process on that square */ if(x<width-1 && occupy[x+1][y] && !handled[x+1][y]) process(x+1,y); /* if the west square is occupied and not handled, call process on that square */ if(x>0 && occupy[x-1][y] && !handled[x-1][y]) process(x-1,y); /* if the north square is occupied and not handled, call process on that square */ if(y<height-1 && occupy[x][y+1] && !handled[x][y+1]) process(x,y+1); /* if the south square is occupied and not handled, call process on that square */ if(y>0 && occupy[x][y-1] && !handled[x][y-1]) process(x,y-1); }
This program does minimal error-checking, and you can enhance it so that no matter what the input file looks like, your program will handle it properly. You can also write a program to generate random input files to test your program.

Inside process() we see that the if statements take advantage of the short-circuit evaluation, which is discussed in Chapter 16.5.

Note that array-out-of-bounds errors are easy to make in this program; so be careful.
Next let’s look at an interesting game – the game of Nim!
◀ Identify Groups on a Board - Step 3▶ Exercise #2: The Game of Nim

fShare
Questions? Let me know!