首页 > 代码库 > HDU - 1728 逃离迷宫（带转弯的dfs）
HDU - 1728 逃离迷宫（带转弯的dfs）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1728
题意：从迷宫的一个点走到另一个点，要求转弯数不能超过k次，并且有可能走不到
典型的走迷宫问题，主要是如何处理转弯和剪枝的问题。转弯的话可以用if(dir!=-1&&i!=dir）来判断。
剪枝：1.找到，返回。
2.超出给定的转弯数，返回
3.刚好到给定的转弯数，但是没到指定要到的点，返回
4.超出给定的地图或碰到障碍物，换个方向走
5.可以从其他路径以更少的转弯次数到达,舍去现在路径，换个方向走
6.转一次后,转弯前转弯数+1还是比现在到达的转弯数大,舍去现在路径，换个方向走
*注意：走过后要把路恢复原样，因为其他路径也可能走这个点。还有就是输入数据的问题，y1>>x1>>y2>>x2;题目要求是这样输入的(-?-;)。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 char map[111][111]; 6 int turn[111][111]; 7 int dx[4]={1,-1,0,0}; 8 int dy[4]={0,0,-1,1}; 9 int m,n,x2,y2,k,ok;10 11 void dfs(int x,int y,int dir){12 int xx,yy;13 if(x==x2&&y==y2&&turn[x][y]<=k) {ok=1;return;}//成功,返回14 if(turn[x][y]>k) return;//转弯数超出范围,返回 15 if(x!=x2&&y!=y2&&turn[x][y]==k) return;//没到达,但是提前到转弯数,返回 16 for(int i=0;i<4;i++){17 xx=x+dx[i];18 yy=y+dy[i];19 if(xx<=0||yy<=0||xx>m||yy>n||map[xx][yy]==‘*‘) continue;//不符合条件,返回20 if(turn[xx][yy]<turn[x][y]) continue;//可以从其他路径以更少的转弯次数到达,舍去现在路径21 //转一次后,转弯前转弯数+1还是比现在到达的转弯数大,舍去现在路径 22 if(dir!=-1&&i!=dir&&turn[xx][yy]<turn[x][y]+1) continue; 23 if(dir!=-1&&i!=dir) turn[xx][yy]=turn[x][y]+1;24 else turn[xx][yy]=turn[x][y];25 map[xx][yy]=‘*‘;26 dfs(xx,yy,i);27 map[xx][yy]=‘.‘;//恢复原来状态,因为其他路径也可能往这边走28 if(ok) return; 29 }30 31 }32 33 int main(){34 int t,x1,y1;35 cin>>t;36 while(t--){37 cin>>m>>n;38 39 for(int i=1;i<=m;i++)40 for(int j=1;j<=n;j++)41 cin>>map[i][j];42 43 cin>>k>>y1>>x1>>y2>>x2;44 memset(turn,0x3f,sizeof(turn));//要求最小值,先初始化为最大值.45 ok=0;46 turn[x1][y1]=0;47 dfs(x1,y1,-1);48 if(ok) cout<<"yes"<<endl;49 else cout<<"no"<<endl;50 }51 return 0;52 }
HDU - 1728 逃离迷宫（带转弯的dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。