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

int try(int row, int col);

#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;

	if (!try(1, 1)) {
		printf("No path starting at 1, 1.\n");
		return EXIT_FAILURE;
	}

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

	return EXIT_SUCCESS;
}

/*
If there is a path from this location to the finish, draw the path with plus
signs.  Return 1 if there is a path, 0 otherwise.
*/

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

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

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

	/* 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] = '+';

	if (try(row + 1, col) ||       /* down */
		try(row - 1, col) ||       /* up */
		try(row, col + 1) ||       /* left */
		try(row, col - 1)) {       /* right */
		return 1;
	}

	/* Our earlier optimism proved to be unfounded. */
	maze[row][col] = ' ';

	return 0;
}