怀化网站优化公司推荐,长春门户网站建设制作,快递网站模版,html网页基本结构沼跃鱼早已看穿了一切 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 593 Solved: 229[Submit][Status][Web Board]Description 沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间#xff0c;墙上的指示牌写着#xff1a;房间内某处有一宝箱#xff0c;但是宝箱被上锁了… 沼跃鱼早已看穿了一切 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 593 Solved: 229[Submit][Status][Web Board] Description 沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间墙上的指示牌写着房间内某处有一宝箱但是宝箱被上锁了钥匙在这个房间的某个角落。沼泽鱼对宝箱里有什么很感兴趣但它必须先去拿到钥匙才可以打开宝箱。然而沼跃鱼早已看穿了一切它看清了这个房间的布局现在给出房间的布局图问沼跃鱼拿到钥匙并打开宝箱最少需要走多少步。沼跃鱼每次只能向上、下、左、右中其中一个方向走一步但若那个位置是墙时则不能往那个位置走显然沼跃鱼不能穿墙。 Input 输入的第一行是一个整数T(0T20),代表接下来有T组数据。 每组数据的第一行有两个整数n,m(0n,m≤10)n代表房间的宽度m代表房间的长度。 接下来n行每行有m个字符‘S’表示开始时沼跃鱼所处的位置‘#’代表墙‘*’代表空地‘K’代表钥匙‘B’表示宝箱。钥匙只有一把。 详情参看样例输入。 Output 对于每组数据输出一行包含一个整数xx代表沼跃鱼拿到钥匙并打开宝箱所需的最少步数。若沼跃鱼不能够拿到钥匙并打开宝箱即到达不了钥匙或宝箱所在处则输出-1。 Sample Input 1 5 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 : #includeiostream
#includecstring
#includecstdio
using namespace std;
int b[15][15];
void bfs(int n,int m,int num)
{for(int i1;in;i){for(int j1;jm;j){if(b[i][j]num){if(b[i][j1]0){b[i][j1]num1;}if(b[i][j-1]0){b[i][j-1]num1;}if(b[i-1][j]0){b[i-1][j]num1;}if(b[i1][j]0){b[i1][j]num1;}}}}
}
int main()
{int N;cinN;while(N--){char a[15][15];int n,m;cinnm;memset(b,-1,sizeof(b));int x0,y0,x1,y1;for(int i1;in;i){ for(int j1;jm;j){cina[i][j];if(a[i][j]!#){b[i][j]0;}if(a[i][j]S){b[i][j]1;}if(a[i][j]K){x0i;y0j;}}}int num1;while(b[x0][y0]0num75){bfs(n,m,num);num;/*for(int i1;in;i){ for (int j1;jm;j){coutb[i][j]\t;}coutendl;}coutendl;*/}if(num74){cout-1endl;continue;}for(int i1;in;i){ for(int j1;jm;j){if(a[i][j]!#){b[i][j]0;}if(a[i][j]K){b[i][j]1;}if(a[i][j]B){x0i;y0j;}}}/* for(int i1;in;i){ for (int j1;jm;j){coutb[i][j]\t;}coutendl;}*/int num01;while(b[x0][y0]0num075){bfs(n,m,num0);num0;///*for(int i1;in;i)//{ // for (int j1;jm;j)// {// coutb[i][j]\t;// }// coutendl;//}*///coutendl;}if(num074){cout-1endl;continue;}coutnumnum0-2endl;}
} 转载于:https://www.cnblogs.com/guofeng1022/p/4220565.html
