Help needed with backtracking
Code:
#include <stdio.h>
/* Entry FREE means the position is free to be traversed.
* Entry WALL means the position can never be traversed.
* Entry USED means the position has already been visited,
* and should not be visited again to avoid running in circles.
* Such entries USED are introduced during the search.
*/
#define FREE 0
#define WALL 1
#define USED 2
/* Our maze. */
#define ROWS 5
#define COLS 7
int maze[ROWS][COLS] =
{ { FREE, WALL, FREE, FREE, FREE, WALL, FREE },
{ FREE, FREE, FREE, WALL, FREE, WALL, FREE },
{ FREE, FREE, WALL, WALL, FREE, FREE, FREE },
{ WALL, FREE, FREE, FREE, WALL, FREE, WALL },
{ FREE, FREE, WALL, FREE, FREE, FREE, FREE } };
/* Initial length of shortest path, which is more than largest
* possible length if any path exists. This value indicates no path exists.
*/
#define NOPATH (ROWS*COLS)
/* Length of shortest path. Initialized to upper bound, which would
* indicate no path exists.
*/
int shortest = NOPATH;
/* Positions of mouse and cheese. */
#define MOUSE_ROW 2
#define MOUSE_COL 1
#define CHEESE_ROW 0
#define CHEESE_COL 6
/* First check if current position exists, and can be traversed (it is FREE),
* and whether current path length is shorter than shortest path.
* If cheese found, record length of path.
* Otherwise, mark current position as used, and try moving up, down, left, right
* by recursive calls, and then make position unused again.
*/
void find_cheese(int row, int col, int length)
{
Complete function
}
int main()
{
find_cheese(MOUSE_ROW, MOUSE_COL, 0);
if (shortest < NOPATH)
printf("Shortest path has length: %d\n", shortest);
else
printf("No path exists\n");
return 0;
}
This is a homework assignment. I have done a search on this forum regarding backtracking and I didn't find anything. What I need to do seems quite simple, completing the code by creating the function, because it's backtracking it has to be a recursive function. However, despite the guidance of the comments, I don't get it. What is meant by "current position"? Íf someone could explain that to me, I can finish the code myself. Thanks