首页 > 代码库 > HDU1010 dfs + 剪枝
HDU1010 dfs + 剪枝
题目大意:
找到一条路到终点的时候的时候正好与给出时间相同，每次移动一个单位都增加一分钟，不能走回头路。
dfs搜索，每次经过一个位置，将visit[x][y] 设为1，表示已访问，记得回溯的时候重新将visit改为0；
这道题很容易TLE，所以要注重剪枝，把所有能退出dfs递归的条件全列举清楚
设置一个flag标记，当找到路的时候就令flag=1；
这里只要输出YES或NO就可以了，所以只要flag=1后就不必再进行dfs递归了
还有根据曼哈顿距离和需要的时间进行比较。曼哈顿距离为dis，时间为t，那么dis>t时候直接退出递归
而且此处要做一个奇偶性剪枝，若(dis-t)&1 == 1那说明永远无法到达那一点
1 //这道题需要大量的剪枝过程，少一个都可能会报错bn 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 char mat[8][8],visit[8][8]; 8 int n,m,t,flag,a,b,c,d; 9 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};10 void dfs(int x,int y,int time)11 {12 visit[x][y]=1;13 if(mat[x][y] == ‘D‘){14 if(time == t)15 flag = 1;16 return;17 }18 19 //接下来两端为两个重要的剪枝过程，避免了大量运算20 int tmp = t - time - abs(c-x) - abs(d-y);21 if(tmp < 0 || tmp&1)22 {23 //cout<<x<<" "<<y<<" "<<time<<" "<<abs(c-x)<<" "<<abs(d-y)<<endl;24 return;25 }26 27 if(time > t)28 return;29 30 for(int i=0;i<4;i++){31 int xx = x+dir[i][0];32 int yy = y+dir[i][1];33 if(xx>=0&&xx<n&&yy>=0&&yy<m&&mat[xx][yy]!=‘X‘&&!visit[xx][yy]){34 dfs(xx,yy,time+1);35 //这里早做判断可以提早退出dfs，避免超时36 if(flag)37 return;38 visit[xx][yy]=0;39 }40 }41 }42 int main()43 {44 while(~scanf("%d%d%d",&n,&m,&t)){45 if(n==0&&m==0&&t==0)46 break;47 48 for(int i=0;i<n;i++)49 for(int j=0;j<m;j++){50 cin>>mat[i][j];51 if(mat[i][j] == ‘S‘)52 a=i,b=j;53 if(mat[i][j] == ‘D‘)54 c=i,d=j;55 }56 57 memset(visit , 0, sizeof(visit));58 flag = 0;59 dfs(a,b,0);60 61 if(flag) puts("YES");62 else puts("NO");63 64 }65 return 0;66 }
HDU1010 dfs + 剪枝
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。