Depth-first search on a 2D grid

find-path.c

/* Tries to find the shortest path to G */

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

#define WIDTH 10
#define HEIGHT 10

const char grid[][WIDTH] =
{
	{'O','.','.','.','.','.','.','.','.','.'},
	{'O','.','.','.','.','.','.','.','G','.'},
	{'O','O','O','O','O','O','O','O','O','O'},
	{'.','.','O','.','.','O','.','.','.','.'},
	{'.','.','O','.','.','O','.','.','.','.'},
	{'.','O','O','O','O','O','.','G','.','.'},
	{'.','O','.','.','O','.','.','.','.','.'},
	{'.','.','.','.','O','.','.','.','.','.'},
	{'.','G','.','.','O','.','.','G','.','.'},
	{'.','.','.','.','0','.','.','.','.','.'}
};
static char read_grid(int x, int y)
{
	return grid[y][x];
}
static bool is_open(int x, int y)
{
	if(y <= -1 || y >= HEIGHT || x <= -1 || x >= WIDTH) return false;
	char c = read_grid(x,y);
	return c == 'O' || c == 'G';
}


struct path_link_t
{
	int x, y;
	struct path_link_t *prev;
};

bool explore(struct path_link_t *prev, int x, int y)
{
	/* Check that we can be here */
	if(!is_open(x, y))
		return false;

	/* Check that we haven't been here before */
	{
		struct path_link_t *p = prev;
		while(p)
		{
			if(p->x == x && p->y == y)
				return false;
			p = p->prev;
		}
	}
	
	struct path_link_t link;
	link.x = x;
	link.y = y;
	link.prev = prev;
	
	/* Check for a win */
	if(read_grid(x,y) == 'G')
	{
		struct path_link_t *win = &link;
		while(win)
		{
			printf("[%d, %d]\n", win->x, win->y);
			win = win->prev;
		}
		return true;
	}

	return 	explore(&link, x, y - 1) ||
			explore(&link, x, y + 1) ||
			explore(&link, x - 1, y) ||
			explore(&link, x + 1, y);
}

int main(int argc, char *argv[])
{
	explore(NULL, 0, 0);
	
	return 0;
}