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