这是一道很好的搜索题。
既然是最大时间与最小时间的差，所以可以先用BFS求出最少时间；再用DFS求出最大时间（但注意要剪枝，不然会超时）。
话不多说，进入正题。
既然可以有四个方向可以走，那么我们可以定义两个方向增量数组，一个记录X，一个记录Y。
像这样：
int dx[5]={1,-1,0,0}, dy[5]={0,0,1,-1};BFS：定义一个队列，分别存X，Y和最小步数。
DFS：用两个量，一个记录行，一个记录列。
更多解释详见代码中的注释。
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std;//头文件，不必多说。 struct Node { int x; int y; int step; }queue[10010];//队列。 int dx[5]={1,-1,0,0}, dy[5]={0,0,1,-1};//方向数组 bool a[1100][1100],vis[1100][1100],pd[1100][1010];//a表示地图，vis为BFS的标记数组，pd为DFS的标记数组。 int n,m,i,j,x,y,zd,zx,f[110][110],dis[110][110]; void bfs () { //广度优先搜索 int head=0,tail=1,nx,ny,i;//head头指针，tail为指针，nx与ny新的点。 queue[tail].x=n; queue[tail].y=1; queue[tail].step=0; vis[n][1]=true; while (head<tail) { head++; for (i=0;i<4;i++) {//枚举四个点。 nx=queue[head].x+dx[i]; ny=queue[head].y+dy[i]; if (nx>=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==false&&a[nx][ny]==true) {//判断这个点是否可取 tail++;//保存这个点和最小步数 queue[tail].x=nx; queue[tail].y=ny; queue[tail].step=queue[head].step+1; vis[nx][ny]=true;//标记这个点已经访问过了，下次不再访问 if (nx==1&&ny==n) { zx=queue[tail].step;//到达了目标状态。 return; } } } } return;//好习惯。 } void check () { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) f[i][j]=dis[i][j]; return; } void dfs (int i,int j) {//深度优先搜索。 if (dis[i][j]>zx&&dis[i][j]<f[i][j]) return; if (i==1&&j==n) { if (dis[i][j]>zd) { zd=dis[i][j]; check (); } return ; } for (int k=0;k<4;k++) {//枚举四个点 int nx=i+dx[k],ny=j+dy[k]; if (nx>0&&ny>0&&nx<=n&&ny<=n&&a[nx][ny]==true&&pd[nx][ny]==false) { pd[nx][ny]=true; dis[nx][ny]=dis[i][j]+1; dfs (nx,ny); pd[nx][ny]=false; dis[nx][ny]=0; } } return; } int main () { memset (a,true,sizeof(a));//初始化。 scanf ("%d%d",&n,&m);//读入。 for (i=1;i<=m;i++) { scanf ("%d%d",&x,&y); a[x][y]=0;//标记不可走 } bfs (); pd[n][1]=true;//注意这一步很重要！！！ dfs (n,1); printf ("%d\n",zd-zx);//输出结果。 return 0; }今天本蒟蒻的题解就写到这里啦！！！
再见啦。▽
来都来了，要不点个赞再走呗？
