You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
84 lines
1.5 KiB
84 lines
1.5 KiB
#include<cstdio>
|
|
#include<iostream>
|
|
#define N 5
|
|
using namespace std;
|
|
|
|
struct note
|
|
{
|
|
int x,y,pre;//存放坐标，前一个节点的位置
|
|
} que[100];
|
|
|
|
int maze[N][N];
|
|
int Nx[4]= {1,-1,0,0}; //x轴变化方向
|
|
int Ny[4]= {0,0,-1,1}; //y轴变化方向
|
|
int start=0,end=1;//用数组模拟一个队列
|
|
|
|
//输出结果
|
|
void print(int s) {
|
|
if(que[s].pre!=-1) {
|
|
//递归输出
|
|
print(que[s].pre);//根据查找前一个的位置来递归
|
|
cout<<"("<<que[s].x<<", "<<que[s].y<<")"<<endl;
|
|
}
|
|
}
|
|
|
|
//宽度优化算法
|
|
void bfsMaze(int x,int y) {
|
|
que[start].pre=-1;
|
|
que[start].x=x;
|
|
que[start].y=y;
|
|
|
|
//队列还有数据的话
|
|
while(start<end) {
|
|
//探索四个位置
|
|
for(int i=0; i<4; i++) {
|
|
int a=Nx[i]+que[start].x;
|
|
int b=Ny[i]+que[start].y;
|
|
if(a<0 || b<0 || a>=N || b>=N || maze[a][b])//如果出界或者遇到墙
|
|
continue;
|
|
else {
|
|
maze[a][b]=-1;//设置已经访问过
|
|
//入队
|
|
que[end].pre=start;
|
|
que[end].x=a;
|
|
que[end].y=b;
|
|
end++;//数组大小
|
|
}
|
|
//如果发现输出结果
|
|
if(a==N-1 && b==N-1)
|
|
print(start);
|
|
}
|
|
start++;
|
|
}
|
|
|
|
}
|
|
int main() {
|
|
// 输入迷宫地图
|
|
// for(i=0;i<N;i++)
|
|
// for(j=0;j<N;j++)
|
|
// scanf("%d",&maze[i][j]);
|
|
|
|
int i,j;
|
|
//从文本文件中读取数据
|
|
FILE *fpRead=fopen("input.txt","r"); //其中"r"是表示 读
|
|
if(fpRead==NULL) {
|
|
return 0;
|
|
}
|
|
for( i=0; i<5; i++) {
|
|
for(j=0; j<5; j++) {
|
|
fscanf(fpRead,"%d",&maze[i][j]);
|
|
printf("%d ",maze[i][j]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
//开始运算
|
|
cout<<"(0, 0)"<<endl;
|
|
bfsMaze(0,0);
|
|
cout<<"("<<N-1<<", "<<N-1<<")"<<endl;
|
|
|
|
return 0;
|
|
}
|
|
|
|
|