E - Tempter of the Bone
题目大意：N 行 M 列 T 时间，看这个doggie是否能在第T秒刚好到达门。S是doggie的起始位置，D是门的位置。
一个带回溯的DFS很好写
但是需要剪枝
第一个剪枝
int temp= T-t-abs(ex-x)-abs(ey-y); 判断能否到达终点，很常见的剪枝if（temp&1）return false 如果temp>0说明可以到达，此时temp代表还有多少时间可以浪费（简单来说用这些时间去绕弯） 但是temp必须为奇数 ，绕弯是需要回来的，一进一出需要消耗两次还有对强的剪枝，如果T>n*m-wall-1 直接输出NO 这里的减1是因为起点不用走#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; char g[10][10]; bool st[10][10]; int T,n,m; int dx[]= {1,0,-1,0},dy[]= {0,-1,0,1}; bool ans; int ex,ey,sx,sy; bool dfs(int x,int y,int t) { if(ans)return true; if(t>T)return false; int temp= T-t-abs(ex-x)-abs(ey-y); if( temp<0||temp&1)return false; if(x==ex&&y==ey&&t==T)return true; for(int i=0; i<4; i++) { if(ans)return true; int nx=x+dx[i]; int ny=y+dy[i]; if(nx<0||nx>=n||ny<0||ny>=m||g[nx][ny]=='X')continue; if(st[nx][ny])continue; st[nx][ny]=true; if(dfs(nx,ny,t+1)) { ans=true; return true; } st[nx][ny]=false; } return false; } int main() { while(cin>>n>>m>>T) { ans=false; int wall=0; memset(st,false,sizeof st); if(n==0&&m==0&&T==0) break; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { char c; cin>>c; g[i][j]=c; if(c=='S')sx=i,sy=j; if(c=='D')ex=i,ey=j; if(c=='X')wall++; } st[sx][sy]=true; if(T>n*m-wall-1)//??????????????????????? { printf("NO\n"); continue; } if( dfs(sx,sy,0)) printf("YES\n"); else printf("NO\n"); } return 0; }
