Logo CloudLunar

“HDU/1010”的版本间的差异

（以“ 分类:深度优先搜索分类:广度优先搜索 ==摘要== {{信息题|Tempter of the Bone|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}6857...”为内容创建页面）
 
小 （→‎代码： 参考资料）
第87行： 第87行：
 
</pre>
 
</pre>
 
|code1010}}
 
|code1010}}
 +
 +
==参考资料和拓展阅读==
 +
<references/>

2015年2月7日 (六) 14:10的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Tempter of the Bone ★☆☆☆☆ 答案正确 100 2015-02-06 14:43:00 无

题意

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

题解

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

奇偶性剪枝

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

显示/移除行号
  1. ((ex+sx+ey+sy+t)%2)//(ex,ey)为终点,(sx,sy)为起点//

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

显示/移除行号
  1.    0    1    0    1    0
  2.    1    0    1    0    1
  3.    0    1    0    1    0
  4.    1    0    1    0    1

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

可行性剪枝

代码如下

显示/移除行号
  1. (abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t)//w代表墙的个数//
  2. 意思是：
  1. 如果直接无视障碍走过去的时间都不只t，那么直接剪枝。
  2. 如果去掉墙所有的位置都走一遍的时间还少于t，那么也直接剪枝。

代码

1010.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<iostream>
  5. #define ci const int &
  6. using namespace std;
  7. const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
  8. bool visited[10][10]={};
  9. char a[10][10]={};
  10. int n,m,t,sx,sy,ex,ey,w=0;
  11. const bool dfs(ci x,ci y,ci t)
  12. {
  13.     if(!t&&a[x][y]=='D')
  14.         return 1;
  15.     if(!t)return 0;
  16.     if(visited[x][y]||a[x][y]!='.')
  17.         return 0;
  18.     visited[x][y]=1;
  19.     for(int i=0;i<4;++i)
  20.     {
  21.         if(dfs(x+dx[i],y+dy[i],t-1))
  22.         {
  23.             visited[x][y]=0;
  24.             return 1;
  25.         }
  26.     }
  27.     visited[x][y]=0;
  28.     return 0;
  29. }
  30. int main()
  31. {
  32.     while(1)
  33.     {
  34.         cin>>n>>m>>t;
  35.         if(!n)
  36.             return 0;
  37.         w=1;
  38.         for(int i=1;i<=n;++i)
  39.         {
  40.             for(int j=1;j<=m;++j)
  41.             {
  42.                 cin>>a[i][j];
  43.                 if(a[i][j]=='S')
  44.                     sx=i,sy=j,a[i][j]='.';
  45.                 if(a[i][j]=='D')
  46.                     ex=i,ey=j;
  47.                 if(a[i][j]=='X')
  48.                     ++w;
  49.             }
  50.         }
  51.         if(((ex+sx+ey+sy+t)&1)||(abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t))//奇偶性剪枝，可行性剪枝//
  52.             cout<<"NO\n";
  53.         else if(dfs(sx,sy,t))
  54.             cout<<"YES\n";
  55.         else
  56.             cout<<"NO\n";
  57.     }
  58. }


参考资料和拓展阅读

  1. 跳转 ↑ http://blog.csdn.net/cyg0810/article/details/8194108
取自“https://blog.CloudLunar.com/index.php?title=HDU/1010&oldid=1081”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]