HDU/1010

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Tempter of the Bone	★★☆☆☆	答案正确	100	2015-02-06 14:43:00	超时（0）

• 来自寒假练习：Only a signing tool ! K题
• 原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题意

在n*m的地图上求从S走到D是否能够恰好t步走完。

题解

显然还是搜索题，裸搜会T，所以要剪枝，加上下面两个剪枝好像就Acceptable了：

奇偶性剪枝

这是不太好想的，我的确用了百度优先搜索……限制语句是这样的

((ex+sx+ey+sy+t)%2)//(ex,ey)为终点,(sx,sy)为起点//

想到这样一个矩阵就比较好理解，x+y为偶数时 为0 否则为1：

   0    1    0    1    0
   1    0    1    0    1
   0    1    0    1    0
   1    0    1    0    1

由图可知，任意一个点相邻的必然是与本身相反的值，也就是说，要想走到与本身值相同的点必然要走偶数步，同理，要想走到与本身相异的值的点必然要走奇数步； 所以，当两个位置的x+y奇偶性相同时（同为0或同为1）若时间为奇数 则必然无法到达；当两个位置的奇偶性不同时（一个为1，另一个为0）若时间为偶数也必不能到达，可以被剪枝。

可行性剪枝

代码如下

(abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t)//w代表墙的个数//
意思是：

1. 如果直接无视障碍走过去的时间都不只t，那么直接剪枝。
2. 如果去掉墙所有的位置都走一遍的时间还少于t，那么也直接剪枝。

代码

1010.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define ci const int & using namespace std; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; bool visited[10][10]={}; char a[10][10]={}; int n,m,t,sx,sy,ex,ey,w=0; const bool dfs(ci x,ci y,ci t) { if(!t&&a[x][y]=='D') return 1; if(!t)return 0; if(visited[x][y]||a[x][y]!='.') return 0; visited[x][y]=1; for(int i=0;i<4;++i) { if(dfs(x+dx[i],y+dy[i],t-1)) { visited[x][y]=0; return 1; } } visited[x][y]=0; return 0; } int main() { while(1) { cin>>n>>m>>t; if(!n) return 0; w=1; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { cin>>a[i][j]; if(a[i][j]=='S') sx=i,sy=j,a[i][j]='.'; if(a[i][j]=='D') ex=i,ey=j; if(a[i][j]=='X') ++w; } } if(((ex+sx+ey+sy+t)&1)||(abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t))//奇偶性剪枝，可行性剪枝// cout<<"NO\n"; else if(dfs(sx,sy,t)) cout<<"YES\n"; else cout<<"NO\n"; } }