USACO DEC08 Problem 'badgras' Analysis

by Fatih Gelgi

Problem can be solved using Breadth First Search (BFS).

The idea is to choose a location first, and traverse the pasture through adjacent bad grass. During the traverse, each location is marked. The number of times that the BFS function is called is the number of islands.

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

/* BFS - O(RC) */

#include <fstream>
#include <queue>

using namespace std;

#define MAX 1000

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];
queue<int> que;

// read file
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 file
void writeFile(char *outFile)
{
	ofstream f;
	f.open(outFile);
	f << cnt << "\n";
	f.close();
}

// main bfs function
void bfs(int y,int x)
{
	que.push(y);
	que.push(x);
	
	do
	{
		y=que.front(); que.pop();
		x=que.front(); que.pop();

		// check all the adjacent cells
		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 the cell is a bad grass and not marked add it to the queue
				if (mat[newY][newX]>0 && !mark[newY][newX])
				{
					mark[newY][newX]=true;	// mark the traversed location
					que.push(newY);
					que.push(newX);
				}
		}
	}
	while (!que.empty());
}

int main()
{
	readFile("badgras.in");

	// look for unmarked bad grass locations
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			// if the location is a bad grass and not marked call 
			//	BFS function and increase the island counter
			if (mat[i][j]>0 && !mark[i][j])
			{
				bfs(i,j);
				cnt++;
			}

	writeFile("badgras.out");
}