奇偶剪枝：把map看作
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
?
從 0->1 需要奇數步
從 1->0 需要偶數步
那么設所在位置 (si,sj) 與 目標位置 (di,dj)
如果abs(si-sj)+abs(di-dj)為偶數，則說明 abs(si-sj) 和 abs(di-dj)的奇偶性相同，需要走偶數步
如果abs(si-sj)+abs(di-dj)為奇數，那么說明 abs(si-sj) 和 abs(di-dj)的奇偶性不同，需要走奇數步
理解為 abs(si-sj)+abs(di-dj) 的奇偶性就確定了所需要的步數的奇偶性！！
而 (t-cnt)表示剩下還需要走的步數，由于題目要求要在 t時 恰好到達，那么? (t-cnt) 與 abs(si-sj)+abs(di-dj) 的奇偶性必須相同
因此 temp=t-cnt-abs(sj-dj)-abs(si-di) 必然為偶數！
?
其實很簡單，就是從一個點到另一個點總會有最短路徑abs(sj-dj)-abs(si-di)，如果你要迂回走，總要走多偶數步才能到達。

#include<stdio.h> #include<math.h> #include<string.h> char s[15][15]; int check[15][15]; int n,m,t; int endi,endj; int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};int dfs(int si,int sj,int sum) {int i,j,k,ch;if(si==endi&&sj==endj&&sum==t)return 1;k=t-sum-fabs(si-endi)-fabs(sj-endj);if(k<0||k%2==1)return 0;if(si<0||sj<0||si>=n||sj>=m)return 0;for(i=0;i<4;i++){if(s[si+dir[i][0]][sj+dir[i][1]]=='.'&&check[si+dir[i][0]][sj+dir[i][1]]!=1){check[si+dir[i][0]][sj+dir[i][1]]=1;ch=dfs(si+dir[i][0],sj+dir[i][1],sum+1);if(ch==1)return 1;check[si+dir[i][0]][sj+dir[i][1]]=0;}}return 0; }int main() {int i,j,k,d,count,si,sj;while(scanf("%d%d%d",&n,&m,&t)>0,n,m,t){if(n==0&&m==0&&t==0) break;getchar();count=0;memset(check,0,sizeof(check));for(i=0;i<n;i++){scanf("%s",s[i]);getchar();}for(i=0;i<n;i++)for(j=0;j<m;j++){if(s[i][j]=='S'){si=i;sj=j;}if(s[i][j]=='D'){endi=i;endj=j;s[i][j]='.';}if(s[i][j]=='X'){count++;check[i][j]=1;}}check[si][sj]=1;if(n*m-count<=t)printf("NO\n");elseif(dfs(si,sj,0)==1)printf("YES\n");elseprintf("NO\n");}return 0; }

?

轉載于:https://www.cnblogs.com/wanru/archive/2013/04/14/3020485.html

總結

以上是生活随笔為你收集整理的hdu1010深搜+奇偶剪枝的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。