Problem 1205 小鼠迷宫问题

2023-12-20 10:40

本文主要是介绍Problem 1205 小鼠迷宫问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

方法二的原作者:https://blog.csdn.net/mengxiang000000/article/details/50850996

Accept: 680    Submit: 2305
Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

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

小鼠的迷宫

编程任务

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

 Input

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

结果输出

 Output

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

 Sample Input

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

 Sample Output

11 96

 Source

FJOI2005

 

估计你百分百卡在了TLE上。做了老长时间了,都快疯了。看了大佬的代码。总结出了两种方式。

首先,超时的原因就是在dfs上。想到剪枝了,但是没什么能剪掉的对吧。这里就可以用大神的方法二变换一种思路来“剪枝”

方法一:

这种方也很巧妙,知识一个小技巧,会让你的dfs少走很多弯路(大佬们的思维岂能是你我所能匹敌。。。。)

在dfs中steps是当前的步数,那么如果此时的位置x,y与(到)终点ex,ey的距离(步数)加上steps大于最小步数了,肯定就不会走这条路了。也是一种剪枝的方法

 方法二:

建立一个step的步数数组。在dfs时,不像我们一开始的思路,找到了最短路就把他返回,而是把step填满(这里可能说的不是很准确,希望你们能理解。。。不删言语啊T-T)。然后再返回。这时候是不是想到了什么?

没错,我们去dfs这个step数组,而且还是凶ex,ey开始往回搜索。为啥呢?

因为,在bfs时,每次走一个点标记一下,那么这个点标记的这个值一定是到这个点的最小步数。当我们都标记玩时。我们从终点开始向起点dfs,只要是dfs的下一个点的标记值-1等于此时这个点,说明就能从那个点走到当前的点。不断的搜索下去,如若那个点等于开始点了。那么路径条数就+1;ok了。

/*-------------方法一-----------------*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include <sstream>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define maxsize 1005int n,m,k;
int sx,sy,ex,ey;    //开始和结束坐标
int vis[maxsize][maxsize];
int hinder[maxsize][maxsize];
int d[][2]={0,1,1,0,0,-1,-1,0};
int cnt,ans;struct Room{int x,y,step;
};bool check(int x,int y){if(x>=1 && x<=n && y>=1 && y<=m){return true;}return false;
}int bfs(struct Room r){if(!check(r.x,r.y)) return 0;if(hinder[r.x][r.y]!=0 || vis[r.x][r.y]!=0) return 0;if(r.x==ex && r.y==ey){return r.step;}queue<struct Room> que;que.push(r);vis[r.x][r.y]=1;while(!que.empty()){struct Room t = que.front();que.pop();vis[t.x][t.y] = 1;if(t.x==ex && t.y==ey){return t.step;}struct Room p;for(int i=0;i<4;i++){p.x = d[i][0]+t.x;p.y = d[i][1]+t.y;p.step = t.step+1;if(check(p.x,p.y) && vis[p.x][p.y]==0 && hinder[p.x][p.y]==0){que.push(p);vis[p.x][p.y]=1;}}}
}void dfs(int x,int y,int steps){if(!check(x,y)) return ;if(vis[x][y]!=0 || hinder[x][y]!=0) return ;if(x==ex && y==ey && steps==ans){cnt++;return ;}if(steps>ans) return ;if(abs(x-ex)+abs(y-ey)+steps>ans) return;vis[x][y] = 1;for(int i=0;i<4;i++){int a = x+d[i][0];int b = y+d[i][1];if(check(a,b) && vis[a][b]==0 && hinder[a][b]==0){dfs(a,b,steps+1);vis[a][b] = 0;}}return ;
}int main(){while(scanf("%d%d%d",&n,&m,&k)!=EOF){cnt = 0;ans = 0;memset(vis,0,sizeof(vis));memset(hinder,0,sizeof(hinder));int a,b;for(int i=0;i<k;i++){scanf("%d%d",&a,&b);hinder[a][b]=1;}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);struct Room r;r.x = sx;r.y = sy;r.step = 0;ans = bfs(r);if(ans!=0) cout<<ans<<endl;else cout<<"No Solution!"<<endl;if(ans!=0){memset(vis,0,sizeof(vis));dfs(sx,sy,0);cout<<cnt<<endl;}}
}
/*-----------------方法二--------------------*/#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct zuobiao
{int x,y;
}now,nex;
int step[105][105];
int a[105][105];
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
int n,m,k;
int sx,sy,ex,ey;
int cont;
void bfs(int x,int y)
{memset(step,0,sizeof(step));step[x][y]=1;now.x=x;now.y=y;queue<zuobiao >s;s.push(now);while(!s.empty()){now=s.front();s.pop();for(int i=0;i<4;i++){nex.x=now.x+fx[i];nex.y=now.y+fy[i];if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&step[nex.x][nex.y]==0&&a[nex.x][nex.y]!=1){step[nex.x][nex.y]=step[now.x][now.y]+1;s.push(nex);}}}
}
void dfs(int x,int y)
{if(x==sx&&y==sy){cont++;return ;}else{for(int i=0;i<4;i++){int xx=x+fx[i];int yy=y+fy[i];if(step[xx][yy]==step[x][y]-1){dfs(xx,yy);}}}
}
int main()
{while(~scanf("%d%d%d",&n,&m,&k)){cont=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){a[i][j]=0;}}while(k--){int x,y;scanf("%d%d",&x,&y);x--;y--;a[x][y]=1;}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);sx--;sy--;ex--;ey--;bfs(sx,sy);printf("%d\n",step[ex][ey]-1);dfs(ex,ey);printf("%d\n",cont);}
}

 

这篇关于Problem 1205 小鼠迷宫问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_40099908/article/details/91889285
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/515737

相关文章

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件:2、死锁示例代码3、如何检测死锁?3.1 使用 jstack3.2

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》:本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》:本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

《如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socketreadtimedout的问题》:本文主要介绍解决Druid线程... 目录异常信息触发场景找到版本发布更新的说明从版本更新信息可以看到该默认逻辑已经去除总结异常信息触发场景复

VS配置好Qt环境之后但无法打开ui界面的问题解决

《VS配置好Qt环境之后但无法打开ui界面的问题解决》本文主要介绍了VS配置好Qt环境之后但无法打开ui界面的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 目UKeLvb录找到Qt安装目录中designer.UKeLvBexe的路径找到vs中的解决方案资源