首页 > 代码库 > HDU 1010 (搜索+奇偶剪枝)
HDU 1010 (搜索+奇偶剪枝)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目大意：给定起点和终点，问刚好在t步时能否到达终点。
解题思路：
4个剪枝。
①dep>t剪枝
②搜到一个解后剪枝
③当前走到终点最少步数>满足条件还需要走的步数剪枝（关键）
③奇偶剪枝(关键)：当前走到终点步数的奇偶性应该与满足条件还需要走的步数奇偶性一致。
其中三四两步放在一步中写：remain=abs(x-ex)+abs(y-ey)-abs(dep-t)
奇偶剪枝的原理：abs(x-ex)+abs(y-ey)为奇，则说明到达终点肯定还要走奇数步，反之偶数步。于是得和abs(dep-t)即还需走的步数奇偶性协调。
所以③④剪枝条件这么写if(remain>0||remain%2) return;
#include "cstdio"#include "string"#include "iostream"#include "cstring"using namespace std;int n,m,t,sx,sy,ex,ey,map[15][15],dir[4][2]={-1,0,1,0,0,-1,0,1};bool vis[15][15],flag;int ABS(int x) {return x<0?-x:x;}void dfs(int x,int y,int dep){ vis[x][y]=true; if(dep>t) return; if(flag) return; if(dep==t&&map[x][y]==3) {flag=true;return;} int remain=ABS(x-ex)+ABS(y-ey)-ABS(dep-t); if(remain>0||remain&1) return; for(int s=0;s<4;s++) { int X=x+dir[s][0],Y=y+dir[s][1]; if(vis[X][Y]||X<0||X>n||Y<0||Y>m||map[X][Y]==0) continue; dfs(X,Y,dep+1); vis[X][Y]=false; }}int main(){ //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); string tt; while(cin>>n>>m>>t&&n) { flag=false; memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) { cin>>tt; for(int j=0;j<tt.size();j++) { if(tt[j]==‘S‘) {map[i][j+1]=2;sx=i;sy=j+1;} if(tt[j]==‘D‘) {map[i][j+1]=3;ex=i;ey=j+1;} if(tt[j]==‘.‘) map[i][j+1]=1; if(tt[j]==‘X‘) map[i][j+1]=0; } } dfs(sx,sy,0); if(flag) printf("YES\n"); else printf("NO\n"); }}
| 11864555 | 2014-10-13 19:36:45 | Accepted | 1010 | 515MS | 284K | 1408B | C++ | Physcal |
HDU 1010 (搜索+奇偶剪枝)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。