hdu 1010 Tempter of the Bone （奇偶性剪枝）

  题意：有一副二维地图'S'为起点，'D'为终点，'.'是可以行走的，'X'是不能行走的。问能否只走T步从S走到D？

  题解：最容易想到的就是DFS暴力搜索，，但是会超时。。。=_=。。。 所以，，要有其他方法适当的剪枝；假设当前所在的位置为(x,y)，终点D的位置为(ex,ey); 那么找下规律可以发现： 当 |x-ex|+|y-ey| 为奇数时，那么不管从(x,y)以何种方式走到(ex,ey)都是花费奇数步；当为偶数时同理。  这即是所谓的奇偶性剪枝。这样剪枝就可以复杂度就变为原来暴力DFS的开根号（原来复杂度不清楚该怎么计算...=_=...）

 1 /**
 2 * @author Wixson
 3 */
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include <set>
15 const int inf=0x3f3f3f3f;
16 const double PI=acos(-1.0);
17 const double EPS=1e-8;
18 using namespace std;
19 typedef long long ll;
20 typedef pair<int,int> P;
21 
22 int n,m,t;
23 char str[10][10];
24 int ans;
25 int sx,sy,ex,ey;
26 int book[10][10];
27 int Next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
28 //
29 int abs(int x)
30 {
31     return x>0?x:-x;
32 }
33 void dfs(int x,int y,int cnt)
34 {
35     if(str[x][y]=='D')
36     {
37         if(cnt==t)
38         {
39             ans=1;
40         }
41         return;
42     }
43     //
44     if(cnt==t) return;
45     //
46     int temp=abs(x-ex)+abs(y-ey);
47     if(temp%2!=(t-cnt)%2) return;
48     //
49     //printf("%d %d  --  %d\n",x,y,cnt);
50     for(int k=0;k<4;k++)
51     {
52         int tx=x+Next[k][0],ty=y+Next[k][1];
53         //
54         if(tx<0||tx>=n||ty<0||ty>=m||book[tx][ty]||str[tx][ty]=='X') continue;
55         //
56         book[tx][ty]=1;
57         dfs(tx,ty,cnt+1);
58         book[tx][ty]=0;
59         if(ans) return;
60     }
61 }
62 //
63 int main()
64 {
65     //freopen("input.txt","r",stdin);
66     while(scanf("%d%d%d",&n,&m,&t)&&(n||m||t))
67     {
68         ans=0;
69         for(int i=0;i"%s",str[i]);
70         //
71         memset(book,0,sizeof(book));
72         for(int i=0;i)
73         {
74             for(int j=0;j)
75             {
76                 if(str[i][j]=='S') sx=i,sy=j;
77                 if(str[i][j]=='D') ex=i,ey=j;
78             }
79         }
80         //
81         book[sx][sy]=1;
82         dfs(sx,sy,0);
83         //
84         if(ans) printf("YES\n");
85         else printf("NO\n");
86     }
87     return 0;
88 }
dfs搜索

相关

docker-compose fastdfs

力扣530题（二叉搜索树的最小绝对差）

hdfs的写入过程和读取过程

快速排序与随机构建二叉搜索树

PyCharm2021使用教程 ---9、PyCharm中的搜索技巧（文件/函数/内容）

广度优先搜索复习笔记

无人机视觉导航搜索资料

find 语句过滤掉某个目录搜索

C#集成FastDFS断点续传

分布式文件服务器FastDFS

Linux搜索指定目录中所有文件的内容

大数据学习之旅1——HDFS版本演化

标签