USACO OPEN07 Problem 'catchcow' Analysis

by Richard Ho

One way to view this problem is to consider each number on the number line as a vertex in a graph, and the edges connect each number to its adjacent numbers as well as twice that number. The problem then becomes the shortest path from N to K on that graph. Since all edges have equal weight (i.e. 1 minute) we can use a simple breadth first search so solve this problem. We visit each vertex in order of distance from the start, using a queue to see what to visit next. This gives us linear time solution. Here is a solution based on the description above.
#include <iostream>
using namespace std;
FILE *in = fopen("catchcow.in", "r"), *out = fopen("catchcow.out", "w");
#define QSIZE 200000
int whereinqueue[QSIZE]; //index of element in queue, -1 if not in queue
int q[QSIZE],qstart,qend; //this is a circular array queue
int dist[QSIZE]; //dist[x] = distance to x from starting position
int n,k;

/*update x in queue, or add if not already in queue and dist==-1*/
void update(int x, int d)
{
	if (whereinqueue[x]==-1 && dist[x]==-1)
	{
		dist[x]=d;
		//add x to the end of queue
		q[qend]=x; whereinqueue[x]=qend;
		qend++; if (qend==QSIZE) qend=0;
	}
}
void processqueue(void) /*process the element at the head of the queue*/
{
	int x=q[qstart],d=dist[q[qstart]];
	//we need to add all places we can reach to the queue
	if (x+1<QSIZE) update(x+1,d+1);
	if (x-1>=0) update(x-1,d+1);
	if (2*x<QSIZE && x!=0) update(2*x,d+1);
	//remove head of queue
	whereinqueue[x]=-1;
	qstart++; if (qstart==QSIZE) qstart=0;
}
int main(void)
{
	int i;
	fscanf(in,"%i %i",&n,&k);
	for (i=0;i<QSIZE;i++) {whereinqueue[i]=-1; dist[i]=-1;}
	q[0]=n; dist[n]=0; qstart=0; qend=1; //start at point n
	while (qstart!=qend) processqueue();
	fprintf(out,"%i\n",dist[k]);
	fclose(in); fclose(out); return 0;
}