欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【BFS】电子老鼠闯迷宫

程序员文章站 2022-03-25 17:01:26
...

时间限制:1000MS内存限制:256000KB

题目描述
如下图12×12方格图,找出一条自入口(2,9)到出口(11,8)的最短路径。

【BFS】电子老鼠闯迷宫

输入
第一行为一个数n,表示迷宫大小
第二行为4个数,表示起点和终点
第三起为n*n的矩阵,0表示通路,1表示墙。

输出
第一行为路径(见样例)
第二行为总的步数

输入:
12 //迷宫大小
2 9 11 8 //起点和终点
1 1 1 1 1 1 1 1 1 1 1 1 //邻接矩阵,0表示通,1表示不通
1 0 0 0 0 0 0 1 0 1 1 1
1 0 1 0 1 1 0 0 0 0 0 1
1 0 1 0 1 1 0 1 1 1 0 1
1 0 1 0 0 0 0 0 1 0 0 1
1 0 1 0 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1 0 0 0 0 1
1 0 1 1 1 0 0 0 1 1 1 1
1 0 0 0 0 0 1 0 0 0 0 1
1 1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1

输出:
(2,9)->(3,9)->(3,8)->(3,7)->(4,7)->(5,7)->(5,6)->(5,5)->(5,4)->(6,4)->(7,4)->(7,3)->(7,2)->(8,2)->(9,2)->(9,3)->(9,4)->(9,5)->(9,6)->(8,6)->(8,7)->(8,8)->(9,8)->(9,9)->(10,9)->(11,9)->(11,8)
27

我的思路:
直接广搜,搜到结果为止

C++代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y,l,r;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};//四个方向
int a[1001][1001];//存储地图与存储步数
int wah[2001][4];
bool check(int x,int y)//判断出界
{
	if(x<0 || y<0 || x>n || y>n)return 0;
	if(a[x][y])return 0;
	return 1; 
}
void out(int k)//输出
{
	if(k!=0)out(wah[k][3]);
	else return;
	printf("(%d,%d)->",wah[k][1],wah[k][2]);
}
int main()
{
	scanf("%d",&n);
	scanf("%d%d%d%d",&x,&y,&l,&r);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	}//读入
	a[x][y]=1;//定义初始值
	wah[1][1]=x;
	wah[1][2]=y;
	int head=1,tail=1;//头与尾
	while(head<=tail)
	{
		for(int i=0;i<4;i++)
			if(check(wah[head][1]+dx[i],wah[head][2]+dy[i]))
			{
				tail++;
				a[wah[head][1]+dx[i]][wah[head][2]+dy[i]]=a[wah[head][1]][wah[head][2]]+1;
				wah[tail][1]=wah[head][1]+dx[i];
				wah[tail][2]=wah[head][2]+dy[i];
				wah[tail][3]=head;
				if(wah[tail][1]==l && wah[tail][2]==r)//看一下是否走到了终点
				{
					out(wah[tail][3]);//输出路径
					printf("(%d,%d)",wah[tail][1],wah[tail][2]);//输出路径
					printf("\n%d",a[l][r]);//输出总步数
					return 0;
				}
			}
		head++;
	}
	return 0;
}
相关标签: BFS