直接搜索會(huì)超時(shí)，需要減枝（奇偶減枝）。

#include<stdio.h> #include<string.h> int n,m,t; char map[7][7]; int x0,y0,x1,y1; int flag; int abs(int a) {a>0?:a=-a; return a; } void dfs(int time,int x,int y) {int temp=time-(abs(x1-x)+abs(y1-y));if(temp<0||temp%2) return;//剩余時(shí)間-距離終點(diǎn)的最小步數(shù) 小于0（夠不到終點(diǎn)）或者 為奇數(shù)（最多能到終點(diǎn)前一個(gè)位置）則返回 else if(time==0) {if(x==x1&&y==y1)flag=1;else return; }if(flag) return;if(x-1>=0&&map[x-1][y]!='X'){map[x-1][y]='X'; dfs(time-1,x-1,y);map[x-1][y]='.'; }if(y-1>=0&&map[x][y-1]!='X'){map[x][y-1]='X';dfs(time-1,x,y-1);map[x][y-1]='.'; }if(x+1<n&&map[x+1][y]!='X'){map[x+1][y]='X';dfs(time-1,x+1,y);map[x+1][y]='.'; }if(y+1<m&&map[x][y+1]!='X'){map[x][y+1]='X';dfs(time-1,x,y+1);map[x][y+1]='.'; }return; } int main(void) {int count;while(scanf("%d%d%d",&n,&m,&t)) {if(n==0&&m==0&&t==0) break;flag=0;count=0;getchar();for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%c",&map[i][j]); if(map[i][j]=='S'){x0=i;y0=j; map[i][j]='X'; } if(map[i][j]=='D'){x1=i;y1=j; count++; } if(map[i][j]=='.') count++;}getchar();}if(t>count||t<abs(x1-x0)+abs(y1-y0)){printf("NO\n");continue; }dfs(t,x0,y0);if(flag) printf("YES\n");else printf("NO\n"); } }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lqquan/p/3671870.html

總結(jié)

以上是生活随笔為你收集整理的HDU1010 Tempter of the Bone dfs（奇偶减枝）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。