#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int** CreateTwoDimensionalArr(int a, int b)//动态创建二位数组。。
{
int i;
int **p;
p = (int**)malloc(sizeof(int*) * a);
if (p == NULL)
{
printf("内存分配失败,程序强制退出。。");
exit(1);
}
for (i = 0; i < a; i++)
{
p[i] = (int*)malloc(sizeof(int) * b);
if (p[i] == NULL)
{
printf("内存分配失败,程序强制退出。。");
exit(1);
}
}
return (p);
}
void FreeTwoDimensionalArr(int **p, int a, int b)//释放动态分配的内存。。
{
int i;
for (i = 0; i < a; i++)//释放动态分配的内存。。
{
free(p[i]);
}
free(p);
}
void main()
{
int m;//迷宫行数。。
int n;//迷宫列数。。
int **MAZE;//迷宫。。
int **MARK;//标志。。
int **Q;//记录路线。。
int **RECORD;//记录最短路径。。
int MOVE[9][3] = {2, 2, 2,
2,-1, 0,
2,-1, 1,
2, 0, 1,
2, 1, 1,
2, 1, 0,
2, 1,-1,
2, 0,-1,
2,-1,-1};
int i;
int j;
int minSteps = m * n;//记录最短路径长度。。
int tempM;
int tempN;
printf("请输入迷宫的大小:\nm=");
scanf("%d", &m);
printf("n=");
scanf("%d", &n);
MAZE = CreateTwoDimensionalArr(m + 2, n + 2);
MARK = CreateTwoDimensionalArr(m + 1, n + 1);
Q = CreateTwoDimensionalArr(m * n, 4);
for (j = 0; j < n + 2; j++)//设置迷宫的墙壁。。
{
MAZE[0][j] = 1;
MAZE[m + 1][j] = 1;
}
for (i = 0; i < m + 2; i++)
{
MAZE[i][0] = 1;
MAZE[i][n + 1] = 1;
}
srand((int)time(NULL));//以系统当前时间设置随机数函数的种子。。
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
MAZE[i][j] = rand() % 2;//随机生成迷宫。。
MARK[i][j] = 0;//标志初始化为0。。
}
}
MAZE[1][1] = 0;//迷宫入口出口设置为可通过。。
MAZE[m][n] = 0;
MARK[1][1] = 1;
Q[1][0] = 1;//记录出发地点的坐标。。
Q[1][1] = 1;
Q[1][2] = 1;
for (i = 2; i < m * n; i++)
{
Q[i][2] = 0;
}
for (i = 1; i < m + 1; i++)
{
for (j = 1; j < n + 1; j++)
{
printf("%d", MAZE[i][j]);//输出迷宫。。
}
printf("\n");
}
i = 1;
while (Q[1][2] <= 8)
{
if ((Q[i][0] == m) && (Q[i][1]) == n)
{
if (i - 1 < minSteps)
{
minSteps = i - 1;
for (j = 1; j <= minSteps; j++)
{
Q[j][3] = Q[j][2];
}
}
MARK[m][n] = 0;
Q[i][2] = 0;
i--;
Q[i][2]++;
}
else
{
tempM = Q[i][0] + MOVE[Q[i][2]][1];//下一步的m。。
tempN = Q[i][1] + MOVE[Q[i][2]][2];//下一步的n。。
if ((MAZE[tempM][tempN] == 0) && (MARK[tempM][tempN] == 0))
{
i++;
MARK[tempM][tempN] = 1;
Q[i][0] = tempM;
Q[i][1] = tempN;
Q[i][2] = 1;
}
else
{
Q[i][2]++;
while ((Q[i][2] > 8) && (i != 1))
{
MARK[Q[i][0]][Q[i][1]] = 0;
Q[i][2] = 0;
i--;
Q[i][2]++;
}
}
}
}
if (minSteps == m * n)
{
printf("THERE IS NO PATH.");
} else
{
tempM = m;
tempN = n;
printf("(%d,%d)", m, n);
for (j = minSteps; j >= 1; j--)
{
tempM = tempM - MOVE[Q[j][3]][1];
tempN = tempN - MOVE[Q[j][3]][2];
printf("(%d,%d)", tempM, tempN);
}
}
printf("\n");
FreeTwoDimensionalArr(MAZE, m + 2, n + 2);//释放。。
FreeTwoDimensionalArr(MARK, m + 1, n + 1);
FreeTwoDimensionalArr(Q, m * n, 3);
}