#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct node{ int x,y,step,time; }; int map[10][10],n,m; int bx,by; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1}; void bfs() { queue<node>q; node t={bx,by,0,6};//起点的状态 q.push(t); while(!q.empty()) { node p; p=q.front(); q.pop(); for(int i=0;i<4;i++) { t.x=dx[i]+p.x; t.y=dy[i]+p.y; t.step=p.step+1; t.time=p.time-1; if(t.x>=0&&t.x<n&&t.y>=0&&t.y<m&&t.time>0&&map[t.x][t.y]!=0)//可行走的情况 { if(map[t.x][t.y]==3)//到达终点，就是最短时间 { cout<<t.step<<endl; return ; } if(map[t.x][t.y]==4)//遇到重置设备 { t.time=6; map[t.x][t.y]=0; } q.push(t); } } } cout<<-1<<endl;//始终没有搜索到终点，不能到达 return ; } int main() { int t; cin>>t; while(t--) { cin>>n>>m; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>map[i][j]; if(map[i][j]==2) { bx=i,by=j;//起点 } } } bfs(); } return 0; }
而dfs的思路稍微复杂些，要考虑用重置设备后要返回的情况。但是我们可以知道如果要重复走走过的路，他的消耗时间一定多了，但剩下的时间一定要比原来多才有用。要不然剩下的时间少了，消耗的时间多了，谁会干着这种吃力不讨好的事？
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #define inf 0x3f3f3f3f using namespace std; int n,m,map[10][10],step[10][10],time[10][10],flag,ans; int bx,by,ex,ey; void dfs(int x,int y,int sum,int T)//sum为花费时间，T为还剩的时间 { if(T<=0||map[x][y]==0||x<0||x>=n||y<0||y>=m)//不合法和不可行的情况 return ; //cout<<x<<" "<<y<<endl; if(x==ex&&y==ey)//遇到终点 { flag=1;//标记 ans=min(ans,sum);//取最小时间 return ; } if(map[x][y]==4)//遇到重置设备 T=6; if(sum>=step[x][y]&&time[x][y]>=T)//走已经走过的路，但剩下的时间少于原来的时间就不会走 return ; step[x][y]=sum;//更新这一步的消耗时间和剩余时间 time[x][y]=T; dfs(x,y-1,sum+1,T-1);//左 dfs(x,y+1,sum+1,T-1);//右 dfs(x-1,y,sum+1,T-1);//下 dfs(x+1,y,sum+1,T-1);//上 } int main() { int t; cin>>t; while(t--) { flag=0; ans=inf; cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) { time[i][j]=0; step[i][j]=inf; cin>>map[i][j]; if(map[i][j]==2)//起点 { bx=i; by=j; } if(map[i][j]==3)//终点 { ex=i; ey=j; } } dfs(bx,by,0,6); if(flag==0) cout<<-1<<endl; else cout<<ans<<endl; } return 0; }
原文：https://www.cnblogs.com/xiongtao/p/9382143.html