小鼠迷宫问题

最新推荐文章于 2024-05-14 21:23:02 发布

acm_JL

最新推荐文章于 2024-05-14 21:23:02 发布

阅读量3.3k

点赞数

分类专栏： DFS BFS

本文链接：https://blog.csdn.net/acm_JL/article/details/50853895

版权

DFS 同时被 2 个专栏收录

12 篇文章

订阅专栏

BFS

9 篇文章

订阅专栏

问题描述

小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。

编程任务

对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。

输入：

本题有多组输入数据，你必须处理到EOF为止。
每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。(1≤p,r≤n; 1≤q,s≤m)

输出：

对于每组数据，将计算出的小鼠a通向小鼠b的最短路长度和有多少条不同的最短路输出。每组数据输出两行，第一行是最短路长度；第2行是不同的最短路数。每组输出之间没有空行。
如果小鼠a无法通向小鼠b则输出“No Solution!”。

Input

8 8 3
3 3
4 5
6 6
2 1
7 7

Output

11
96

分析：利用bfs可以计算出最短路径的距离len（即移动次数），然后用dfs计算出等于len（移动次数）时有多少种不同的最短路径。

#include<string.h>
#include<iostream>
using namespace std;
struct note
{
	int x;//横坐标
	int y;//纵坐标
	int s;//走的步数 
};
struct note que[2051];
int i,j,k,h,n,m,startx,starty,p,q,ty,tx,flag,ans=0,count=0,an,bn;
int a[51][51],book[51][51],book2[51][51];
int next[4][2]={{0,1},
				{1,0},
				{0,-1},
				{-1,0}};
int bfs()
{ 
	//队列初始化
	int head=1;
	int tail=1;
	//往队列插入迷宫的入口坐标
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].s=0;
	tail++;
	book[startx][starty]=1;
	flag=0;//用来标记是否到达目的地，0表示没有
	while(head<tail)//当队列不为空时候 
	{
		//枚举四个方向(注意方向数组的设置和for循环的遍历，通用模板)
		for(h=0;h<=3;h++)
		{
			//计算下一个点坐标
		     tx=que[head].x+next[h][0];
			 ty=que[head].y+next[h][1];
			 //判断是否越界
			 if(tx<1||tx>n||ty<1||ty>m)
			 	continue;
			//判断是否是障碍物或者已经在路径中
			if(a[tx][ty]==0&&book[tx][ty]==0)
			{
				//把这个点标记为已经走过
				//注意宽带搜索每个点只能入队列一次 ，和dfs不同，所以book的值不需要恢复为0；
				book[tx][ty]=1;
				//插入新的点到队列中
				que[tail].x =tx;
				que[tail].y=ty;
			    que[tail].s=que[head].s+1;
				tail++; 
			 } 
			 //如果到了目的地，停止扩展，任务结束，退出循环
			 if(tx==p&&ty==q)
			 	return que[tail-1].s; 
		} 
		 head++;
	 } 
	 //打印队列中末尾最后一个点的步数
	 //注意tail是指向队尾的下一个位置，所以需要-1
	 	 	
 } 
void  dfs(int x,int y,int step)//dfs的作用是用来处理当前这一步怎么走 
{
		int tx,ty,k;
		if(x==p&&y==q&&step==ans)//到达小红位置 
		{
			count++;
			return ;
		}
		if(step>ans)
			return ;
		//未到达位置向四个方向走
		for(k=0;k<=3;k++)
		{
		//计算下一个点坐标 
		tx=x+next[k][0];
		ty=y+next[k][1];
		//判断是否越界
		if(tx<1||tx>n||ty<1||ty>m)
			continue;
		//判断该点是否是障碍物或者已经在路径中
		if(a[tx][ty]==0&&book2[tx][ty]==0) 
		{
			book2[tx][ty]=1;//标记这个点已经走过 
			dfs(tx,ty,step+1);//开始尝试下一个点 
			book2[tx][ty]=0;//尝试结束，取消标记 
		}
	 } 
	
	}


int main()
{
	cin>>n>>m>>k;
	for(i=1;i<=k;i++)
	{
		cin>>an>>bn;
		a[an][bn]=1;		
	}
	cin>>startx>>starty;
	cin>>p>>q;
	ans=bfs();//求得最少步数 ，调用bfs后book数组的标记不是初始化为0了，对dfs的影响很大，故应在调用bfs之前将book恢复初始化 
 	cout<<"最短路径长度是："<<ans<<endl; 
 	book2[startx][starty]=1;//标记起点防止重复走 
	dfs(startx,starty,0);
	cout<<"最短路径的个数是："<<count<<endl;
	return 0;
 }