首页 > 代码库 > 沼跃鱼早已看穿了一切 C/C++
沼跃鱼早已看穿了一切 C/C++
沼跃鱼早已看穿了一切
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 593 Solved: 229
[Submit][Status][Web Board]
Description
沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间，墙上的指示牌写着：房间内某处有一宝箱，但是宝箱被上锁了，钥匙在这个房间的某个角落。沼泽鱼对宝箱里有什么很感兴趣，但它必须先去拿到钥匙才可以打开宝箱。然而沼跃鱼早已看穿了一切，它看清了这个房间的布局，现在给出房间的布局图，问沼跃鱼拿到钥匙并打开宝箱最少需要走多少步。沼跃鱼每次只能向上、下、左、右中其中一个方向走一步，但若那个位置是墙时则不能往那个位置走（显然，沼跃鱼不能穿墙）。
Input
输入的第一行是一个整数T(0<T<20),代表接下来有T组数据。
每组数据的第一行有两个整数n,m(0<n,m≤10)，n代表房间的宽度，m代表房间的长度。
接下来n行，每行有m个字符，‘S’表示开始时沼跃鱼所处的位置，‘#’代表墙，‘*’代表空地，‘K’代表钥匙，‘B’表示宝箱。钥匙只有一把。
详情参看样例输入。
Output
对于每组数据，输出一行包含一个整数x，x代表沼跃鱼拿到钥匙并打开宝箱所需的最少步数。若沼跃鱼不能够拿到钥匙并打开宝箱（即到达不了钥匙或宝箱所在处）则输出-1。
Sample Input
15 6***#B#S**#*###***#K#*#*#***#*#
Sample Output
17
HINT
对于样例数据，房间宽5个单位，长6个单位。
从S出发到K需要的最少步数为8，而从K出发到B所需的最少步数为9.
所以答案为8 + 9 = 17.
请使用scanf("%s", s);或cin>> s;来读取字符串以避免出现漏读多读的情况。
BFS 广度优先搜索
CODE :
#include<iostream>#include<cstring>#include<cstdio>using namespace std;int b[15][15];void bfs(int n,int m,int num){ for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(b[i][j]==num) { if(b[i][j+1]==0) { b[i][j+1]=num+1; } if(b[i][j-1]==0){ b[i][j-1]=num+1; } if(b[i-1][j]==0){ b[i-1][j]=num+1; } if(b[i+1][j]==0){ b[i+1][j]=num+1; } } } }}int main(){ int N; cin>>N; while(N--) { char a[15][15]; int n,m; cin>>n>>m; memset(b,-1,sizeof(b)); int x0,y0,x1,y1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]!=‘#‘) { b[i][j]=0; } if(a[i][j]==‘S‘) { b[i][j]=1; } if(a[i][j]==‘K‘) { x0=i; y0=j; } } } int num=1; while(b[x0][y0]==0&&num<75) { bfs(n,m,num); num++; /*for(int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cout<<b[i][j]<<‘\t‘; } cout<<endl; } cout<<endl;*/ } if(num>74) { cout<<"-1"<<endl; continue; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]!=‘#‘) { b[i][j]=0; } if(a[i][j]==‘K‘) { b[i][j]=1; } if(a[i][j]==‘B‘) { x0=i; y0=j; } } } /* for(int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cout<<b[i][j]<<‘\t‘; } cout<<endl; }*/ int num0=1; while(b[x0][y0]==0&&num0<75) { bfs(n,m,num0); num0++; ///*for(int i=1;i<=n;i++) //{ // for (int j=1;j<=m;j++) // { // cout<<b[i][j]<<‘\t‘; // } // cout<<endl; //}*/ //cout<<endl; } if(num0>74) { cout<<"-1"<<endl; continue; } cout<<num+num0-2<<endl; }}
沼跃鱼早已看穿了一切 C/C++
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。