//本程序求解<迷宫指路>
//By Optimistic
Q1:如何设计程序数据?
A1:一般我们用一个2维数组表示这个迷宫 0代表路 1代表墙
Q2:从A点搜到B点 再搜B点 不又搜到A点了吗?
A1:当我们从A点搜到B点之后 A点就把0改成1 不就变成墙了吗 就不会再搜回去了
Q3:这样不是只能搜到出口 但是不知道具体的路吗?
A1:有两种解决的办法
1.从A点搜到B点 就记录B点的前驱是A 这样我们从出口一路找前驱就可以找到一条路 (本程序采用)
2.我们搜的时候 记录下从入口到此被搜结点的距离 这样我们从出口一路找距离越来越小的结点
也可以找到回入口的路
Q4:要是搜到了边界的0位置怎么办呢?
A1:自然的写法是每次都判断是不是到了边界 不要边界外的子结点
比较有创意的写法是给边界外面加一道围墙 即增设标记为"1"的附加方格(本程序采用)
Q5:...
A1:程序看不懂的地方可以直接来问我... 加油...
*/
#include <stdio.h>
const int M = 8, N = 8; //棋盘的行数 列数(默认为8*8的迷宫 可随意改变)
struct Point
{
int x, y; //方格在棋盘里的行和列
};
struct Queue
{
int front; //队首
int rear; //队尾
Point d[4*M*N]; //元素 这个范围是我想了想定的 应该够了
}Q;
int board[M+2][N+2]; //棋盘
Point start, end; //起点和终点
Point pre[M][N]; //记录结点的前驱
Point offset[4]; //相对位移
bool findPath();
void print();
int main()
{
// freopen("BFS.in", "r", stdin);
offset[0].x = 0, offset[0].y = 1;
offset[1].x = 1, offset[1].y = 0;
offset[2].x = 0, offset[2].y = -1;
offset[3].x = -1, offset[3].y = 0;
int i;
printf("Enter the grid in row-major order:\n");
for(i=1; i<=M; i++)
for(int j=1; j<=N; j++)
scanf("%d", &board[i][j]);
printf("Enter the start position:\n");
scanf("%d%d", &start.x, &start.y);
printf("Enter the end position:\n");
scanf("%d%d", &end.x, &end.y);
if(findPath()) print();
else printf("There is no such road from START to END.\n");
return 0;
}
bool findPath() //搜索从start到end的一条通路 找到返回true 否则返回false
{
if(start.x == end.x && start.y == end.y)
{
pre[end.x][end.y] = end;
return true;
}
//设置棋盘外一圈"围墙"
for(int i=0; i<=M+1; i++)
{
board[0][i] = board[M+1][i] = 1;
board[i][0] = board[i][N+1] = 1;
}
Point cur = start; //current position
Point np = start; //new position
while(1)
{
for(i=0; i<4; i++)
{
np.x = cur.x + offset[i].x;
np.y = cur.y + offset[i].y;
if(board[np.x][np.y] == 0) //通路
{
pre[np.x][np.y] = cur;
if((np.x == end.x) && (np.y == end.y)) break;
Q.d[Q.rear] = np;
Q.rear = (Q.rear+1)%(4*M*N);
board[cur.x][cur.y] = 1;
}
}
if((np.x == end.x) && (np.y == end.y)) break;
if(Q.rear == Q.front) return false;
cur = Q.d[Q.front];
Q.front = (Q.front+1)%(4*M*N);
}
}
void print()
{
printf("One path:\n");
Point ans[M*N];
int ansLen = 0;
Point cur = end;
ans[ansLen++] = cur;
while(cur.x != start.x || cur.y != start.y)
{
cur = pre[cur.x][cur.y];
ans[ansLen] = cur;
ansLen++;
}
int i;
for(i = ansLen-1; i>=0; i--)
{
printf("(%d,%d) ", ans[i].x, ans[i].y);
if((i+1)%5==0) printf("\n");
}
printf("\n");
}
/*
Sample Input:
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
1 0 0 1 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 0 0 1 1 1
1 1 1 1 0 0 1 1
1 1 1 1 1 0 0 1
1 1 1 1 1 1 0 0
1 1
8 8
Sample Output:
One Path:
(1,1) (2,1) (2,2) (3,2) (3,3)
(4,3) (4,4) (5,4) (5,5) (6,5)
(6,6) (7,6) (7,7) (8,7) (8,8)
*/
回复 更多评论