http://acm.hdu.edu.cn/showproblem.php?pid=1010
翻译：有只狗被困了，S是起点，D是门，W是墙不能走，‘ . ’是可以走的路，走一次就会在1秒内坍塌，也就是不能停留也不能走回头路，门只在第T秒打开，问是否能逃命？
解题：一开始以为是三维bfs，但是地图上的时间维度是错误的，因为走过一次地面坍塌，只能有一个时间维度。百度找了居然一个bfs都没有，不得不用dfs，无限超时，甚至记忆化搜索也超时。见识到了高端的剪枝。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #define ll long long #define inf 0x3f3f3f3f using namespace std; bool vis[10][10]; char a[10][10]; int d[4][2]={ {-1,0}, {1,0}, {0,-1}, {0,1} };///上下左右 int n,m,T,cnt; bool flag; struct node { int x; int y; int t; }; node door,start; void dfs(int x,int y,int t)///当前用了多少时间 { if( x==door.x && y==door.y && t==door.t ) { flag=true; return ; } for(int i=0;i<4;i++) { int cha=T-t-abs(door.x-x)-abs(door.y-y);///核心代码 int xx=x+d[i][0]; int yy=y+d[i][1]; int tt=t+1; if( !flag && xx>=0 && xx<n && yy>=0 && yy<m && !vis[xx][yy] && (a[xx][yy]=='.'||a[xx][yy]=='D') && cha>=0 && cha%2==0 ) { vis[xx][yy]=true; dfs(xx,yy,tt); vis[xx][yy]=false; } } } int main()///HDU1010 { while(scanf("%d%d%d",&n,&m,&T) && (n+m+T) ) { memset(a,0,sizeof(a)); memset(vis,false,sizeof(vis)); flag=false; for(int i=0;i<n;i++) scanf("%s",a[i]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { if( a[i][j]=='D' )///终点 door.x=i,door.y=j,door.t=T; if( a[i][j]=='S' )///起点 { start.x=i,start.y=j,start.t=0; vis[ start.x ][ start.y ] = true; } } dfs( start.x,start.y,0 ); if(flag) printf("YES "); else printf("NO "); } return 0; }
dfs内，x和y表示当前坐标，t表示当前花了多少时间。
当前步数到终点的最短距离：abs(door.x-x)+abs(door.y-y)
还需要花的时间：T-t
走最短路的话还剩余的时间：cha = T - t - abs(door.x-x) + abs(door.y-y)
在没有障碍的情况下，cha至少要等于0，如果有障碍，cha要大于0，剪枝剪掉那些 就算没障碍走最短路也走不到的情况。
奇偶剪枝：
举例：
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
假设红色1要走到蓝色1，最短只需要走2步，但是现在有4步，必须绕远，绕过粉色1和粉色0走到蓝色1，如果是3步，怎么走都走不到。