题目链接：Nightmare
题意：
给出一张n*m的图，0代表墙，1代表可以走，2代表起始点，3代表终点，4代表炸弹重置点
问是否能从起点到达终点
分析：
一道很好的DFS题目，炸弹重置点必然最多走一次，可能会陷入无限递归，故有一个重要的剪枝，见代码，
此题采用记忆化搜索（不懂の），注意代码的设计思路
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int t,n,m,a[10][10],step[10][10],T[10][10],sx,sy,ex,ey,cnt,d[4][2]={0,-1,-1,0,1,0,0,1}; 7 8 void dfs(int x,int y,int ste,int time) 9 { 10 if(time==0) return ; 11 if(a[x][y]==3) {cnt=min(ste,cnt);return ;} 12 if(a[x][y]==4) time=6; 13 if(ste>=step[x][y]&&time<=T[x][y]) return ; 14 step[x][y]=ste,T[x][y]=time; 15 for(int i=0;i<4;++i) 16 { 17 int xx=x+d[i][0],yy=y+d[i][1]; 18 if(xx>n||yy>m||xx<1||yy<1||a[xx][yy]==0) continue; 19 //if(step[x][y]<(step[xx][yy]-1)&&T[x][y]>(T[xx][yy]+1)) continue; 20 dfs(xx,yy,ste+1,time-1); 21 } 22 } 23 24 int main() 25 { 26 for(scanf("%d",&t);t--;) 27 { 28 scanf("%d %d",&n,&m); 29 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j) 30 { 31 scanf("%d",&a[i][j]); 32 if(a[i][j]==2) sx=i,sy=j; 33 if(a[i][j]==3) ex=i,ey=j; 34 step[i][j]=0x3f3f3f3f,T[i][j]=0; 35 } 36 cnt=0x3f3f3f3f; 37 dfs(sx,sy,0,6); 38 if(cnt==0x3f3f3f3f) puts("-1");else printf("%d ",cnt); 39 } 40 return 0; 41 }