#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define M 1000
#define N 1000
int MAZE[M + 1][N + 1];
int MARK[M][N];
int Q[M * N - 1][4];
int H[3][3];
int m, n;
int T[100];
typedef struct
{
int line;
int road[100][2];
}Node;
void road(int m, int n)
{
Node Count[100];
int i, j, k, l, p;
p = 0;
for (i = 0; i < m + 2; i++)
{
for (j = 0; j < n + 2; j++)
{
MARK[i][j] = 1;
}
}
for (i = 1; i < m + 1; i++)
{
for (j = 1; j < n + 1; j++)
{
MARK[i][j] = 0;
}
} //初始化mark数组
for (i = 1; i < n + 1; i++)
{
for (j = 1; j < m + 1; j++)
{
MAZE[i][j] = rand() % 2;
}
}
for (j = 0; j < m + 2; j++)
{
MAZE[0][j] = 1;
MAZE[n + 1][j] = 1;
}
for (j = 0; j < n + 2; j++)
{
MAZE[j][0] = 1;
MAZE[j][m + 1] = 1;
} //初始化maze数组
for (i = 1; i < m + 1; i++)
{
for (j = 1; j < n + 1; j++)
{
for (k = i - 1; k < 3; k++)
{
for (l = j - 1; l < 3; l++)
{
H[k][l] = MAZE[k][l];
if (H[k][l] = 0 && MARK[k][l] != 1)
{
Q[p][0] = k;
Q[p][1] = l;
Q[p][2] = i;
Q[p][3] = j;
p++;
}
if (H[k][l] = 1)
{
MARK[k][l] = 1;
}
}
}
}
} //初始化Q数组
int x, y, z, w, t, c, h;
c = 0;
for (i = 0; i < M; i++)
{
t = 2; k = 2; h = 0;
if (Q[i][0] == m && Q[i][1] == n)
{
x = Q[i][2];
y = Q[i][3];
Count[c].road[0][0] = m;
Count[c].road[0][1] = n;
Count[c].road[1][0] = x;
Count[c].road[1][1] = y;
Count[c].line = t;
for (j = h; j < M; j++)
{
if (Q[j][0] == x && Q[j][1] == y)
{
x = Q[j][2];
y = Q[j][3];
Count[c].road[k][0] = x;
Count[c].road[k][1] = y;
Count[c].line = t + 1;
k++;
z = x; w = y;
h = 0;
}
if (Q[j][2] == 1 && Q[j][3] == 1)
{
break;
}
}
c++;
}
}//初始化Count数组
k = 0; p = 1; int min = Count[k].line;
for (i = 0; i < c-1; i++)
{
if (Count[k].line >Count[p].line)
{
min= Count[p].line;
k = p; p++;
}
else
{
p++;
}
} //比较出最短路径
printf("最短路径是:\n");
for (i = 0; i < min; i++)
{
printf("(%d,%d),", Count[k].road[i][0], Count[k].road[i][1]);
}
}
int main()
{
printf("请输入迷宫的行数m,列数n:\n");
scanf_s("%d,%d" ,& m,&n);
road(m, n);
}