Overfencing

This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two “exits” for the maze. Even more happily, the maze he created by this overfencing experience is a ‘perfect’ maze: you can find a way out of the maze from any point inside it.

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the ‘worst’ point in the maze (the point that is ‘farther’ from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move “out” of the maze.

Here’s what one particular W=5, H=3 maze looks like:

+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.

PROGRAM NAME: maze1

INPUT FORMAT

Lines 1:	W and H, space separated
*Lines 2 through 2H+2:**	2*W+1 characters that represent the maze

SAMPLE INPUT (file maze1.in)

5 3
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

OUTPUT FORMAT

A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.

SAMPLE OUTPUT (file maze1.out)

The lower left-hand corner is nine steps from the closest exit.

CODE

Java

C++

Pascal

ANALYSIS

Russ Cox

We can solve this with a standard flood fill, using a queue to implement breadth first search. It is convenient to leave the maze in its ASCII format and just look at it as a bunch of characters, with non-space characters being walls.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAXWID 38
#define MAXHT 100

typedef struct Point Point;
struct Point {
	int r, c;
};

int wid, ht;
char maze[MAXHT*2+1][MAXWID*2+1+2];	/* extra +2 for "\n\0" */
int dist[MAXHT*2+1][MAXWID*2+1];

Point
Pt(int r, int c)
{
    Point p;

    p.r = r;
    p.c = c;
    return p;
}

typedef struct Queue Queue;
struct Queue {
    Point p;
    int d;
};

Queue floodq[MAXHT*MAXWID];
int bq, eq;

/* if no wall between point p and point np, add np to queue with distance d+1 */
void
addqueue(int d, Point p, Point np)
{
    if(maze[(p.r+np.r)/2][(p.c+np.c)/2] == ' ' && maze[np.r][np.c] == ' ') {
	maze[np.r][np.c] = '*';
	floodq[eq].p = np;
	floodq[eq].d = d+1;
	eq++;
    }
}

/* if there is an exit at point exitp, plug it and record a start point
 * at startp */

void
lookexit(Point exitp, Point startp)
{
    if(maze[exitp.r][exitp.c] == ' ') {
	addqueue(0, startp, startp);
	maze[exitp.r][exitp.c] = '#';
    }
}

void
main(void)
{
    FILE *fin, *fout;
    Point p;
    int i, r, c, m, d;

    fin = fopen("maze1.in", "r");
    fout = fopen("maze1.out", "w");
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%d %d\n", &wid, &ht);
    wid = 2*wid+1;
    ht = 2*ht+1;

    for(i=0; i<ht; i++)
	fgets(maze[i], sizeof(maze[i]), fin);

    /* find exits */
    for(i=1; i<wid; i+=2) {
	lookexit(Pt(0, i), Pt(1, i));
	lookexit(Pt(ht-1, i), Pt(ht-2, i));
    }
    for(i=1; i<ht; i+=2) {
	lookexit(Pt(i, 0), Pt(i, 1));
	lookexit(Pt(i, wid-1), Pt(i, wid-2));
    }

    /* must have found at least one square with an exit */
    /* since two exits might open onto the same square, perhaps eq == 1 */
    assert(eq == 1 || eq == 2);	

    for(bq = 0; bq < eq; bq++) {
	p = floodq[bq].p;
	d = floodq[bq].d;
	dist[p.r][p.c] = d;

	addqueue(d, p, Pt(p.r-2, p.c));
	addqueue(d, p, Pt(p.r+2, p.c));
	addqueue(d, p, Pt(p.r, p.c-2));
	addqueue(d, p, Pt(p.r, p.c+2));
    }

    /* find maximum distance */
    m = 0;
    for(r=0; r<ht; r++)
    for(c=0; c<wid; c++)
	if(dist[r][c] > m)
	    m = dist[r][c];

    fprintf(fout, "%d\n", m);

    exit(0);
}