首页 > 代码库 > 一道广搜寻路题
一道广搜寻路题
同样是在qq群里看到的题目，想了好久算法，实现也用了很久。
关于题目首先看图：
总的来说，就是一个二维迷宫的寻路，迷宫中有对应的钥匙和刺，每走一步会消耗1点Hp，当走到刺上时会额外消耗100点hp，持有对应颜色的钥匙通过刺时不用额外消耗Hp。
给予起点和终点的坐标，，输出移动方式，让人物抵达终点所消耗的Hp尽可能的小。
例子：
3 3 1
..a
##A
...
1 1
3 3
这个是输入数据 第一个代表高 第二个宽 第三个是钥匙和陷阱的对数 .代表平地 #代表墙 小写字母是钥匙 大写字母是对应的陷阱
输出为
R
R
D
D
接下去是算法考虑：
关于迷宫寻路，我的第一反应自然是bfs（广搜），比起dfs（深搜），广搜有着每个点仅遍历一次的优点。
比起传统的迷宫寻路，这个迷宫寻路多了钥匙和陷阱方面的因素，在面对陷阱时如何找到对应的钥匙是算法的关键。
这里给上我个人的思路：
通过从小到大增加自身hp，不断的找到可以抵达的地点，一旦找到了终点，那么停止程序输出结果。
对于钥匙和普通地面，将其加入“可抵达点”集合时，与普通bfs的做法相同即可。
对于刺，首先判断如果此时自身的Hp已经有了101多余，那么意味着无需去寻找钥匙，直接强行传过刺是更好的选择。
hp多余不足101的场合，查看能否抵达刺对应钥匙的坐标？(即钥匙是否已经被找到)
如果没找到钥匙，那么就跳过，否则，以钥匙为起点进行第二次寻路。这次寻路的目标是，找到“起点到刺的路径”，所以要对刺在的位置进行一次回溯，获取之前走过的所有路径，然后再进行一次简单的dfs，获取dfs的路程，那么获取钥匙所需的hp就是这次dfs的长度
*2。
由于钥匙到刺的路径是固定的，而你去取钥匙过刺的话，需要进行很多次判定（直到hp增加到够你取钥匙为止）（如果你没看懂这句话，说明没有看懂这个算法...），所以我们也可以把钥匙到刺的路径保存起来，这样能省很多效率。
下面是我写的代码，写的很丑陋请见谅，可以看到有很多被注释的输出用的语句...因为那时候电脑上没有编译环境，就下了一个轻量级的，结果不能debug...
using System; using System.Collections.Generic; class Program { static int[,] map;//记录地图元素 static int[,] s_map;//记录步数 static int height,width,key_num,start_x,start_y,end_x,end_y; static int[,] key;//记录钥匙对应的刺所在的位置 static string[] s_key;//记录对应钥匙到达刺所需的移动方式，输出用 static List<int> list=new List<int>();//bfs中可拓展的节点 static List<int> outlist=new List<int>();//记录找钥匙时插入的节点，输出用 static List<int> outlist2=new List<int>(); static bool find=false; static void Main(string[] args){ getinput(); //output(); list.Add(start_x*width+start_y); s_map[start_x,start_y]=0; findway(0); /*for (int i=0;i<height;i++){ Console.WriteLine(); for (int j=0;j<width;j++){ Console.Write(s_map[i,j]+" "); } }*/ //Console.WriteLine(s_map[end_x,end_y]); //int step=s_map[end_x,end_y]; int x=end_x,y=end_y; string output=""; while(true){ //Console.WriteLine(x+" "+y+" "+output); //Console.ReadKey(); if ((x==start_x)&&(y==start_y)) break; for(int i=outlist.Count-1;i>=0;i--){ int ox=outlist[i]/width; int oy=outlist[i]%width; //Console.WriteLine(ox+" "+oy); //Console.ReadKey(); if(x==ox&&y==oy){ /*for (int j=0;j<outlist.Count;j++){ Console.WriteLine(outlist.Count+" "+outlist[j]+" "+outlist2[j]+" "+s_key[outlist2[j]]); }*/ string s=s_key[outlist2[i]]; output+=s; for (int j=s.Length-1;j>=0;j--){ if (‘L‘==s[j]) output+="R"; if (‘R‘==s[j]) output+="L"; if (‘D‘==s[j]) output+="U"; if (‘U‘==s[j]) output+="D"; } outlist.RemoveAt(i); outlist2.RemoveAt(i); //Console.WriteLine(output+" "+outlist.Count); } } if ((map[x,y]>0)&&map[x,y]<30){//刺的场合 if (x>0) if(s_map[x-1,y]==s_map[x,y]-101){x=x-1;output+="D";continue;} if (y>0) if(s_map[x,y-1]==s_map[x,y]-101){y=y-1;output+="R";continue;} if (x<height-1) if (s_map[x+1,y]==s_map[x,y]-101){x=x+1;output+="U";continue;} if (y<width-1) if (s_map[x,y+1]==s_map[x,y]-101){y=y+1;output+="L";continue;}//如果不是强穿的话 if (x>0) if(s_map[x-1,y]==s_map[x,y]-key[map[x,y],4]*2-1){outlist.Add(key[map[x,y],5]);outlist2.Add(map[x,y]);x=x-1;output+="D";continue;} if (y>0) if(s_map[x,y-1]==s_map[x,y]-key[map[x,y],4]*2-1){outlist.Add(key[map[x,y],5]);outlist2.Add(map[x,y]);y=y-1;output+="R";continue;} if (x<height-1) if (s_map[x+1,y]==s_map[x,y]-key[map[x,y],4]*2-1){outlist.Add(key[map[x,y],5]);outlist2.Add(map[x,y]);x=x+1;output+="U";continue;} if (y<width-1) if (s_map[x,y+1]==s_map[x,y]-key[map[x,y],4]*2-1){outlist.Add(key[map[x,y],5]);outlist2.Add(map[x,y]);y=y+1;output+="L";continue;} } else{ //Console.WriteLine(s_map[x,y+1]+" "+s_map[x,y]); if (x>0) if(s_map[x-1,y]==s_map[x,y]-1){x=x-1;output+="D";continue;} if (y>0) if(s_map[x,y-1]==s_map[x,y]-1){y=y-1;output+="R";continue;} if (x<height-1) if (s_map[x+1,y]==s_map[x,y]-1){x=x+1;output+="U";continue;} if (y<width-1) if (s_map[x,y+1]==s_map[x,y]-1){y=y+1;output+="L";continue;} } } for (int i=output.Length-1;i>=0;i--) Console.WriteLine(output[i]); Console.ReadKey(); } static void findway(int hp){ int x,y; bool bo; for (int i=list.Count-1;i>=0;i--){ x=list[i]/width; y=list[i]%width; bo=true; if (x>0) if (!check(x-1,y,hp,s_map[x,y])) bo=false; if (y>0) if (!check(x,y-1,hp,s_map[x,y])) bo=false; if (x<height-1) if (!check(x+1,y,hp,s_map[x,y])) bo=false; if (y<width-1) if (!check(x,y+1,hp,s_map[x,y])) bo=false; if (bo) list.RemoveAt(i); } if (!find) findway(++hp); } static bool check(int x,int y,int hp,int v){ //Console.WriteLine(x+" "+y+" "+hp+" "+v+" "+find); //Console.WriteLine((x)+" "+(y)+" "+map[x,y]+" "+hp+" "+list.Count); if ((x==end_x)&&(y==end_y))find=true; if (s_map[x,y]!=-1) return true; if (-1==map[x,y]) {return true;}else if (0==map[x,y]){//普通地面的情况下 if (hp==v+1){ s_map[x,y]=hp; list.Add(x*width+y); //Console.WriteLine(x+" "+y); //Console.ReadKey(); return true; }else {return false;} }else if (map[x,y]<30){//刺的情况下 if (hp==v+101){//能否强穿？ s_map[x,y]=hp; list.Add(x*width+y); //Console.WriteLine(x+" "+y); //Console.ReadKey(); return true; }else{//去找钥匙 int key_x=key[map[x,y],0]; int key_y=key[map[x,y],1];//获取钥匙坐标 if(s_map[key_x,key_y]!=-1){//是否找到了钥匙? if (key[map[x,y],4]==0)//将bfs得到的数据保存起来 { bool[,] boolmap=new bool[height,width]; int bo_x=x,bo_y=y; s_map[x,y]=100000; while (!(bo_x==start_x&&bo_y==start_y)){ //Console.WriteLine(bo_x+" "+bo_y); //Console.ReadKey(); boolmap[bo_x,bo_y]=true; if (bo_x>0) if(s_map[bo_x-1,bo_y]<s_map[bo_x,bo_y]&&s_map[bo_x-1,bo_y]!=-1){bo_x=bo_x-1;continue;} if (bo_y>0) if (s_map[bo_x,bo_y-1]<s_map[bo_x,bo_y]&&s_map[bo_x,bo_y-1]!=-1){bo_y=bo_y-1;continue;} if (bo_x<height-1) if (s_map[bo_x+1,bo_y]<s_map[bo_x,bo_y]&&s_map[bo_x+1,bo_y]!=-1){bo_x=bo_x+1;continue;} if (bo_y<width-1) if (s_map[bo_x,bo_y+1]<s_map[bo_x,bo_y]&&s_map[bo_x,bo_y+1]!=-1){bo_y=bo_y+1;continue;} } boolmap[bo_x,bo_y]=true; s_map[x,y]=-1; key[map[x,y],4]=bfs(key_x,key_y,x,y,map[x,y],boolmap); //Console.WriteLine(key[map[x,y],4]); //Console.WriteLine(s_key[map[x,y]]); } if (hp==v+key[map[x,y],4]*2+1){ s_map[x,y]=hp; list.Add(x*width+y); //Console.WriteLine(x+" "+y); //Console.ReadKey(); return true; }else return false; }else return false; } }else{//钥匙的情况下,与普通地面相同 if (hp==v+1){ s_map[x,y]=hp; list.Add(x*width+y); //Console.WriteLine(x+" "+y); //Console.ReadKey(); return true; }else return false; } } static int bfs(int start_x,int start_y,int end_x,int end_y,int q,bool[,] boolmap){ /*for (int i=0;i<height;i++){ Console.WriteLine(); for (int j=0;j<width;j++){ Console.Write((boolmap[i,j]?1:0)+" "); } }*/ //Console.ReadKey(); int[,] bfsmap=new int[height,width]; List<int> bfslist=new List<int>(); bfslist.Add(start_x*width+start_y); bfsmap[start_x,start_y]=1;//为了图方便，直接把起点设置为1 int step=2; int x=0,y=0; bool bo=false; while (true){ for (int i=bfslist.Count-1;i>=0;i--){ x=bfslist[i]/width; y=bfslist[i]%width; if (boolmap[x,y]) {bo=true;break;} if (x>0) if(bfsmap[x-1,y]==0&&map[x-1,y]!=-1) {bfsmap[x-1,y]=step;bfslist.Add((x-1)*width+y);} if (x<height-1) if(bfsmap[x+1,y]==0&&map[x+1,y]!=-1) {bfsmap[x+1,y]=step;bfslist.Add((x+1)*width+y);} if (y>0) if (bfsmap[x,y-1]==0&&map[x,y-1]!=-1) {bfsmap[x,y-1]=step;bfslist.Add(x*width+y-1);} if (y<width-1) if(bfsmap[x,y+1]==0&&map[x,y+1]!=-1) {bfsmap[x,y+1]=step;bfslist.Add(x*width+y+1);} bfslist.RemoveAt(i); } if (bo) break; step++; } //x=end_x;y=end_y; /*for (int i=0;i<height;i++){ Console.WriteLine(); for (int j=0;j<width;j++){ Console.Write(bfsmap[i,j]+" "); } }*/ //Console.WriteLine(step); //Console.ReadKey(); key[map[end_x,end_y],5]=x*width+y;//钥匙插入的节点 s_key[q]=""; for (int i=step-1;i>1;i--){ if (x>0) if(bfsmap[x-1,y]==i-1){x=x-1;s_key[q]+="D";continue;} if (y>0) if(bfsmap[x,y-1]==i-1){y=y-1;s_key[q]+="R";continue;} if (x<height-1) if (bfsmap[x+1,y]==i-1){x=x+1;s_key[q]+="U";continue;} if (y<width-1) if (bfsmap[x,y+1]==i-1){y=y+1;s_key[q]+="L";continue;} } //Console.WriteLine(s_key[q]+" "+q); //Console.ReadKey(); return(step-2); } static void getinput(){ string str=Console.ReadLine(); string[] nums = str.Split(‘ ‘); height=int.Parse(nums[0]); width=int.Parse(nums[1]); key_num=int.Parse(nums[2]); map=new int[height,width]; s_map=new int[height,width]; key=new int[key_num+1,6]; s_key=new string[key_num+1]; for (int i=0;i<height;i++){ str=Console.ReadLine(); for (int j=0;j<width;j++){ if (‘#‘==str[j]) map[i,j]=-1; else if (‘.‘==str[j]) map[i,j]=0; else{ map[i,j]=(int)str[j]-(int)‘A‘+1; if (map[i,j]<30){//大写字母表示刺 key[map[i,j],2]=i; key[map[i,j],3]=j; }else{ key[map[i,j]-32,0]=i;//大小写差32,小写字母表示钥匙 key[map[i,j]-32,1]=j; } } s_map[i,j]=-1;//用最大数充填步数计数 } } str=Console.ReadLine(); nums = str.Split(‘ ‘); start_y=int.Parse(nums[0])-1; start_x=int.Parse(nums[1])-1; str=Console.ReadLine(); nums = str.Split(‘ ‘); end_y=int.Parse(nums[0])-1; end_x=int.Parse(nums[1])-1; } static void output(){ for (int i=0;i<height;i++){ for (int j=0;j<width;j++){ Console.Write(map[i,j]+" "); } Console.WriteLine(); } for (int i=1;i<key_num+1;i++){ Console.Write(key[i,0]+" "+key[i,1]+" "+key[i,2]+" "+key[i,3]+" "); } } }
然后附一张提交结果图，第十六位那个就是我啦~可以看到目前最优的算法应该是总和4000步
那么有什么样的情况没考虑到呢？
一个是我的程序没有把算法完全实现，在遇到这样的情况时：
...ab
.####
A####
B....
从左上走到右下，我的实现里，取钥匙b的时候会重新回到起点，而不是走到a，这样就平白多走了四步，这个优化起来应该不难。
另一种错误数据：
5 4 2
.B.a
.###
...b
.###
A...
1 1
4 5
也是从左上走到右下，最优的路径应该是：起点-->b-->B-->a-->A-->终点
但是我这个程序跑出来的结果会强行穿过A，因为在A上面一格会被计数为3，程序在判断过A的时候只需要10点Hp，而实际上却需要20点Hp。判断过A时最初是一直没找到钥匙，在找到钥匙之后hp却过大了，而hp是递增的，永远不会给用钥匙过A的机会（顺便一提就算给了机会结果也是错的）。
出现这个错误的原因是从A返回起点模拟路径失败了，现在我也没想到什么妥善的解决办法，或许在从a开始寻路的时候，如果路径碰到了刺，就需要额外进行判断...不过这样写起来很麻烦，目前也没有这么多时间琢磨这个...如果看到这篇文章的大牛有什么更好的算法的话，欢迎在评论区留言探讨~
一道广搜寻路题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。