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