需要剪枝否則會超時，然后就是基本的深搜了

#include<cstdio> #include<stdio.h> #include<cstdlib> #include<cmath> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<queue> #define INF 0x3f3f3f3f #define MAX 1005using namespace std;char Map[MAX][MAX];int time,n,m,sx,sy,ex,ey,v[4][2]={{1,0},{0,1},{-1,0},{0,-1}},ok;bool check(int x,int y) {if(x>=0 && x<n && y>=0 && y<m && Map[x][y]!='X')return true;return false; }void DFS(int x,int y,int step) {if(x==ex && y==ey && step==time){ok=1;return;}else if(step >= time || ok)return;for(int i=0;i<4;i++){int new_x=x+v[i][0];int new_y=y+v[i][1];if(check(new_x,new_y)){Map[new_x][new_y]='X';DFS(new_x,new_y,step+1);Map[new_x][new_y]='.';}} }int main() {while(scanf("%d%d%d",&n,&m,&time),n+m+time){ok=0;for(int i=0;i<n;i++)scanf("%s",Map[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(Map[i][j]=='S'){sx=i;sy=j;}if(Map[i][j]=='D'){ex=i;ey=j;}}}int k1=abs(sx-ex);int k2=abs(sy-ey);if((time-(k1+k2))%2)//奇偶剪紙 {printf("NO\n");continue;}if(sx==ex && sy==ey){printf("YES\n");continue;}Map[sx][sy]='X';DFS(sx,sy,0);if(ok)printf("YES\n");elseprintf("NO\n");}return 0; } View Code

?

轉載于:https://www.cnblogs.com/alan-W/p/5890216.html

總結

以上是生活随笔為你收集整理的HDU 1010 Tempter of the Bone DFS（奇偶剪枝优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

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