Code:
#include <stdio.h>
#define START 0
#define WALL -1
#define CORR -2
#define END -3
#define SOL -4
int m[101][101], nx, ny;
int print_maze(FILE *outF)
{
/* Print the maze, and return the number of dots printed. */
int ix, iy, ndots = 0;
for (iy = 1; iy <= ny; ++iy) {
for (ix = 1; ix <= nx; ++ix) {
switch (m[ix][iy]) {
case CORR: fprintf(outF, " "); break;
case END: fprintf(outF, "$"); break;
case SOL: fprintf(outF, "."); ++ndots; break;
case START: fprintf(outF, "*"); break;
case WALL: fprintf(outF, "X"); break;
default: fprintf(outF, " ");
}
}
fprintf(outF, "\n");
}
return ndots;
}
void read_maze(FILE *inF)
{
int ix, iy, c = ' ';
for (iy = 1; iy <= ny; ++iy) {
while (c != '\n') c = fgetc(inF);
for (ix = 1; ix <= nx; ++ix) {
c = fgetc(inF);
switch (c) {
case 'X': m[ix][iy] = WALL; break;
case ' ': m[ix][iy] = CORR; break;
case '*': m[ix][iy] = START; break;
case '$': m[ix][iy] = END; break;
}
}
}
}
void retrace(int ix, int iy, int n)
{
if (n == 0) return;
if (ix>1 && m[ix-1][iy]==n) {
m[ix-1][iy] = SOL; retrace(ix-1, iy, n-1);
} else if (ix<nx && m[ix+1][iy]==n) {
m[ix+1][iy] = SOL; retrace(ix+1, iy, n-1);
} else if (iy>1 && m[ix][iy-1]==n) {
m[ix][iy-1] = SOL; retrace(ix, iy-1, n-1);
} else if (iy<ny && m[ix][iy+1]==n) {
m[ix][iy+1] = SOL; retrace(ix, iy+1, n-1);
}
}
int check(int ix, int iy, int n)
{
if (m[ix][iy] == CORR) {
m[ix][iy] = n; return 1;
}
if (m[ix][iy] == END) {
retrace(ix, iy, n-1); return -10;
}
return 0;
}
int solve_maze(void)
{
int ix, iy, anymore, n = 0, status;
do {
++n; anymore = 0;
for (ix = 1; ix <= nx; ++ix) {
for (iy = 1; iy <= ny; ++iy) {
if (m[ix][iy] == n-1) {
status = 0;
if (ix > 1) status += check(ix-1,iy,n);
if (ix < nx) status += check(ix+1,iy,n);
if (iy > 1) status += check(ix,iy-1,n);
if (iy < ny) status += check(ix,iy+1,n);
if (status < 0) return 1;
if (status) anymore = status;
}
}
}
} while (anymore);
return 0;
}
int main(void)
{
FILE *inF = fopen("maze.in", "r"),
*outF = fopen("maze.out", "w");
int n, i, ok, nsteps;
fscanf(inF, "%d", &n);
for (i = 1; i <= n; ++i) {
fscanf(inF, "%d%d", &nx, &ny);
read_maze(inF); ok = solve_maze();
nsteps = print_maze(outF)+1;
if (ok) fprintf(outF, "The optimal path is %d steps.\n", nsteps);
else fprintf(outF, "This maze has no solutions.\n");
}
fclose(inF); fclose(outF);
return 0;
}