首先这道题是一道经典的BFS。非常适合刚刚学习深搜的同学。
现在分析一下这个问题。首先，每周是八个方向。就是一圈。
也就是说入侵的范围关于时间是成辐射型扩散。让求最大时间。
也就是完美的BFS。算出来之后，维护一个最大用时就好。
不过说一句。这个数区范围对于一个不会stl的人来说可以直接手写队列。
好了上代码：
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std;//头文件不说 int dx[8]={0,1,0,-1,1,1,-1,-1}; int dy[8]={1,0,-1,0,1,-1,1,-1};//定义八个方向 int dis[102][102];//储存所需要的时间 int n,m;int ans;//ans是需要维护的最大值。 int head=1;int tail=1;//定义队列。注意队头队尾是1！； bool book[102][102];//图 int q[10002][2];//手写队列，第二维一个是横坐标，一个是纵坐标 int mx;int my;//初始位置 int main() { scanf("%d%d%d%d",&n,&m,&mx,&my);//输入并且处理 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { char now; cin>>now; if(now=='.') book[i][j]=true; else book[i][j]=false; } }//注意我的建图顺序 /* for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { printf("%d ",book[i][j]); } printf("\n"); } *///测试点 q[1][0]=m-my+1;//把起始点压进队列 q[1][1]=mx; dis[my][m-my+1]=0;//初始化 while(head<=tail)//判断是否为空队列 { int now_x=q[head][0]; int now_y=q[head][1]; int tx,ty; head++;//取出队头横纵坐标 for(int i=0;i<8;i++)//八个方向 { tx=now_x+dx[i];ty=now_y+dy[i]; if(book[tx][ty]==true&&!dis[tx][ty]) /* 这里有个小优化。就是判断能不能走之后。如果搜过了（dis[tx][ty]！=0）就可以不搜了。因为一定会重，直接跳过。 */ { dis[tx][ty]=dis[now_x][now_y]+1; q[++tail][0]=tx; q[tail][1]=ty;//判断，更新，入队 } } } /* for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { printf("%d ",dis[i][j]); } printf("\n"); }*///测试数据 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { ans=max(ans,dis[i][j]); } }//找最大值 printf("%d",ans);//输出 return 0;//程序拜拜 }
实际上我最后67行开始可以有一个优化。就是在更新的时候就连ans一起维护了。就像这样
//54行开始 if(book[tx][ty]==true&&!dis[tx][ty]) { dis[tx][ty]=dis[now_x][now_y]+1; ans=max(ans,dis[tx][ty]); q[++tail][0]=tx; q[tail][1]=ty; } } } printf("%d",ans); return 0;