USACO NOV08 Problem 'guard' Analysis

by Fatih Gelgi

This is a classic FloodFill question.

The idea is to choose a location first, and traverse through adjacent locations with the same height. If that height is the peak, there cannot be any higher location adjacent to the traversed locations. The idea can be considered as traversing the contour line of the given location in a contour map. The process is executed for all unvisited locations to detect all the peaks.

The algorithm visits each location once and checks all adjacent cells hence requires O(N*M) running time. Since it uses only two NxM matrices, and a queue with maximum size of N*M, it requires O(N*M) memory.

#include <fstream>
#include <queue>

using namespace std;

#define MAX 1000

// 8 directions of the adjacent cells
const int dir[8][2]={{-1,-1},{-1,0},{-1,1},{1,-1},{1,0},{1,1},{0,-1},{0,1}};

int N,M,mat[MAX][MAX],cnt;
bool mark[MAX][MAX];		// marker matrix for floodfill
queue<int> que;		// floodfill queue

// read input
void readFile(char *inpFile)
{
	ifstream f;
	f.open(inpFile);
	f >> N >> M;
	for (int i=0; i<N; i++)
		for (int j=0; j<M; j++) f >> mat[i][j];
	f.close();
}

// write peak counts
void writeFile(char *outFile)
{
	ofstream f;
	f.open(outFile);
	f << cnt << "\n";
	f.close();
}

// floodfill algorithm
void floodfill(int y,int x)
{
	// add first location to the queue
	que.push(y);
	que.push(x);

	bool peak=true;

	// floodfill loop for the connected locations
	//	that have the same height with the current location
	do
	{
		// get the next location in the queue
		y=que.front(); que.pop();
		x=que.front(); que.pop();

		// check all adjacent locations
		for (int i=0; i<8; i++)
		{
			int newY=y+dir[i][0],newX=x+dir[i][1];
			if (newY>=0 && newX>=0 && newY<n && newX<m)
				// if an adjacent location is higher
				//	the current location is not a peak
				if (mat[y][x]<mat[newY][newX]) peak=false;
				// if an adjacent location has the same height
				//	add it into the queue to visit
				else if (mat[y][x]==mat[newY][newX] && !mark[newY][newX])
				{
					mark[newY][newX]=true;	// mark the locations in the queue
					que.push(newY);
					que.push(newX);
				}
		}
	}
	while (!que.empty());

	if (peak) cnt++;	// if the current height is peak, increment the peak counter
}

int main()
{
	readFile("guard.in");
	
	for (int i=0; i<N; i++)
		for (int j=0; j<M; j++)
			// visit any land that is not visited
			if (mat[i][j]>0 && !mark[i][j]) floodfill(i,j);
	
	writeFile("guard.out");
}