http://acm.hdu.edu.cn/showproblem.php?pid=1010
题目本身不难，但是不剪枝肯定会超时，还有很多细节要注意，希望能够通过更多的训练加强自己这一方面的能力，使细致成为习惯
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 #define M 100 5 #define mem0(f) memset(f,0,sizeof(f)) 6 char s[M][M]; 7 int n,m,t;//还要把访问的都给标记一下，不能回走的 8 //int ts;//花掉的时间 9 int ok;//ok用来判断是否可以逃生 10 int abs(int a) 11 { 12 if(a>0)return a; 13 return -a; 14 } 15 char bj[M][M]; 16 void dfs(int x,int y,int ts) 17 { 18 if(x<0||y<0||x>=n||y>=m||s[x][y]=='X'||ok==1||bj[x][y]==1||ts>t) 19 return; 20 if(s[x][y]=='D'&&ts==t)ok=1; 21 bj[x][y]=1; 22 if(ok!=1) 23 { 24 dfs(x,y+1,ts+1); 25 dfs(x,y-1,ts+1); 26 dfs(x-1,y,ts+1); 27 dfs(x+1,y,ts+1); 28 bj[x][y]=0;//此路不通 29 } 30 } 31 int main() 32 { 33 int x1,y1,x2,y2; 34 int test; 35 while(cin>>n>>m>>t) 36 { 37 ok=0; 38 mem0(s); 39 mem0(bj); 40 if(!n&&!m&&!t)break; 41 for(int i=0;i<n;i++) 42 for(int k=0;k<m;k++) 43 { 44 cin>>s[i][k]; 45 if(s[i][k]=='S'){x1=i;y1=k;} 46 if(s[i][k]=='D'){x2=i;y2=k;} 47 } 48 //剪枝 49 test=t-abs(x2-x1)-abs(y2-y1);//擦 啊 擦 ，竟然忘记了取绝对值，晕死,果然是水平太低 50 if(test<0)ok=0; 51 else if(test%2)ok=0; 52 else{ 53 for(int i=0;i<n;i++) 54 for(int k=0;k<m;k++) 55 { 56 if(s[i][k]=='S') 57 { 58 dfs(i,k,0); 59 i=n+1; 60 break; 61 } 62 }} 63 if(ok==1)cout<<"YES "; 64 else cout<<"NO "; 65 } 66 return 0; 67 } 68 //这个题目的核心代码算是出来了，但是要是不剪枝的话，肯定超时 69 /*考虑到时间限制， 70 1，最短时间小于t则不可能 71 2,时间有多，多的时间不是2的倍数也不可能*/
如果考虑到走过的点不能再走， biaoji这个数组其实可以不开，只需要把走过的点标记为“X”就行，走不通的话，重新标记为“.”，这样的话在存储上又会有一点优化。