#include <stdio.h>
#include <stdlib.h>
#include <limits.h>	/* for INT_MAX */

int try(int row, int col, int draw);

#define MAXCOL 17
char maze[][MAXCOL] = {
	"XXXXXXXXXXXXXXXXX",
	"X   XXXXXXXXXXXXX",
	"X XXXXXXXXXXXXXXX",
	"X XXXXXXXXXXXXXXX",
	"X   XXXXXXXXXXXXX",
	"X X XXXXXXXXXXXXX",
	"X X XXXXXXXXXXXXX",
	"XXX XXXXXXX    XX",
	"XXX XXXXXXX XX XX",
	"XXX         XX XX",
	"XXX XXX XXX XXXXX",
	"X   XXX XXX X   X",
	"X XXXXX XXX X X X",
	"X   XXX XXX XfX X",
	"XXX XXX XXXXXXX X",
	"XXX             X",
	"XXXXXXXXXXXXXXXXX"
};
#define MAXROW (sizeof maze / sizeof maze[0])

int main()
{
	int row;
	int col;
	const int length =  try(1, 1, 1);

	if (length == INT_MAX) {
		printf("No path starting at 1, 1.\n");
		return EXIT_FAILURE;
	}

	printf("A shortest path is of length %d.\n\n", length);

	for (row = 0; row < MAXROW; ++row) {
		for (col = 0; col < MAXCOL; ++col) {
			printf("%c", maze[row][col]);
		}
		printf("\n");
	}

	return EXIT_SUCCESS;
}

/*
Return the length of the shortest path from this location to the finish.
If there is no path, return INT_MAX.
Draw the path if the third argument is non-zero.
*/

int try(int row, int col, int draw)
{
	typedef struct {
		int drow;
		int dcol;
	} direction_t;

	static const direction_t a[] = {
		{-1,	 0},   /* down */
		{ 1,	 0},   /* up */
		{ 0,	-1},   /* left */
		{ 0,	 1}    /* right */
	};
#define MAXDIRECTION (sizeof a / sizeof a[0])

	const direction_t *p;
	const direction_t *direction;
	int min = INT_MAX;

	/* If we're off the board, */
	if (row < 0 || row >= MAXROW || col < 0 || col >= MAXCOL) {
		return INT_MAX;
	}

	/* If we're already at the "finish", */
	if (maze[row][col] == 'f') {
		return 0;
	}

	/* If this location is already occupied by an 'X' or '+', */
	if (maze[row][col] != ' ') {
		return INT_MAX;
	}

	/* Arrive here if we're at an empty location on the board.
	Optimistically assume that it's the first step of a path leading to the
	finish. */
	maze[row][col] = '+';

	for (p = a; p < a + MAXDIRECTION; ++p) {
		const int length = try(row + p->drow, col + p->dcol, 0);
		if (length < min) {
			direction = p;
			min = length;
		}
	}

	/* Our earlier optimism proved to be unfounded. */
	if (min == INT_MAX) {
		maze[row][col] = ' ';
		return INT_MAX;
	}

	if (draw) {
		/* Now that we've identified the first step from here along the
		shortest path, draw the rest of the path. */
		try(row + direction->drow, col + direction->dcol, draw);
	} else {
		/* If we're not supposed to draw, erase what we drew. */
		maze[row][col] = ' ';
	}

	return min + 1;
}