Code:
#include <stdio.h>
#include <stdlib.h>
#define NUMROWS 20
#define NUMCOLS 20
#define INFINITY 999999
int read_maze(char [][], int *, int *);
void display_maze(char [][]);
void copy_maze(char [][], char[][]);
void solve_maze(char [][], int, int, int);
char mazeBest[NUMROWS][NUMCOLS]; /* Stores best maze found so far. */
int lengthBest = INFINITY; /* Stores length of best maze found so far. */
int main(int argc, char **argv){
FILE *outFile = fopen("pathfile.txt", "w");
char maze[NUMROWS][NUMCOLS]; /* Stores maze read from input file. */
int startRow, startCol; /* Starting point in maze. */
if (read_maze(maze, &startRow, &startCol) == 0)
{
printf("Error reading maze from file robotfile.txt!\n");
return;
}
printf("Starting maze:\n");
display_maze(maze);
solve_maze(maze, startRow, startCol, 0);
if (lengthBest == INFINITY)
{
printf("\nNo path to goal was found in maze!\n");
return;
}
else
{
printf("\nBest solution found:\n");
display_maze(mazeBest);
}
return;
}
/*
* Read maze from "robotfile.txt".
* Fill in *sRow and *sCol with position of 'O'.
* If error, return 0, else return 1.
*/
int read_maze(char maze[NUMROWS][NUMCOLS], int *sRow, int *sCol)
{
char filename;
printf("Enter the name of the maze file. \n");
scanf("%s", filename);
FILE *inFile = fopen("filename", "r");
int row, col;
/* Open maze text file, make sure it opens OK. */
if ((inFile = fopen("robotfile.txt", "r")) == NULL)
{
char filename;
printf("Enter the name of the maze file. \n");
scanf("%s", filename);
FILE *inFile = fopen("filename", "r");
int row, col;
/* Open maze text file, make sure it opens OK. */
if ((inFile = fopen("robotfile.txt", "r")) == NULL)
return 0;
/* Loop through the rows. */
for (row = 0; row < NUMROWS; row++)
{
/* Loop through the column in current row. */
for (col = 0; col < NUMROWS; col++)
{
maze[row][col] = getc(inFile);
/* Check if this is the starting position. */
if (maze[row][col] == 'O')
{
*sRow = row;
*sCol = col;
}
}
/* Ignore newline at end of each row. */
getc(inFile);
}
fclose(inFile);
return 1;
}
/* Display the maze passed as a parameter to standard output. */
void display_maze(char maze[NUMROWS][NUMCOLS])
{
int row, col;
for (row = 0; row < NUMROWS; row++)
{
for (col = 0; col < NUMCOLS; col++)
{
putchar(maze[row][col]);
}
putchar('\n');
}
return;
}
/* Copy the maze in mazeSrc to mazeDest. */
void copy_maze(char mazeSrc[NUMROWS][NUMCOLS],
char mazeDest[NUMROWS][NUMCOLS])
{
int row, col;
for (row = 0; row < NUMROWS; row++)
{
for (col = 0; col < NUMCOLS; col++)
{
mazeDest[row][col] = mazeSrc[row][col];
}
}
return;
}
/*
* Given:
* (1) maze with path so far
* (2) current row
* (3) current column
* (4) length of path so far
* The function solve_maze recursively tries to solve the maze.
*
* When a solution is found, compare it to previous best found solution,
* and update appropriate globals if necessary.
*/
void solve_maze(char mazeCur[NUMROWS][NUMCOLS], int curRow, int curCol,
int length)
{
/* If already as long as best solution, no need to look further. */
if (length >= lengthBest)
return;
/* Check if solution found. */
if ((mazeCur[curRow-1][curCol] == 'X') ||
(mazeCur[curRow+1][curCol] == 'X') ||
(mazeCur[curRow][curCol+1] == 'X') ||
(mazeCur[curRow][curCol-1] == 'X'))
{
/* Found solution, better then previous best, update globals. */
lengthBest = length;
copy_maze(mazeCur, mazeBest);
return;
}
/* Recurse in each possible direction that is empty. */
if (mazeCur[curRow-1][curCol] == ' ')
{
mazeCur[curRow-1][curCol] = 'O';
solve_maze(mazeCur, curRow-1, curCol, length+1);
mazeCur[curRow-1][curCol] = ' ';
}
if (mazeCur[curRow+1][curCol] == ' ')
{
mazeCur[curRow+1][curCol] = 'O';
solve_maze(mazeCur, curRow+1, curCol, length+1);
mazeCur[curRow+1][curCol] = ' ';
}
if (mazeCur[curRow][curCol-1] == ' ')
{
mazeCur[curRow][curCol-1] = 'O';
solve_maze(mazeCur, curRow, curCol-1, length+1);
mazeCur[curRow][curCol-1] = ' ';
}
if (mazeCur[curRow][curCol+1] == ' ')
{
mazeCur[curRow][curCol+1] = 'O';
solve_maze(mazeCur, curRow, curCol+1, length+1);
mazeCur[curRow][curCol+1] = ' ';
}
return;
}