LYK 快跑！(run)
Time Limit:5000ms Memory Limit:64MB
题目描述
LYK 陷进了一个迷宫！ 这个迷宫是网格图形状的。 LYK 一开始在(1,1)位置， 出口在(n,m)。
而且这个迷宫里有很多怪兽，若第 a 行第 b 列有一个怪兽，且此时 LYK 处于第 c 行 d 列，此
时这个怪兽对它的威胁程度为|a-c|+|b-d|。
LYK 想找到一条路径，使得它能从(1,1)到达(n,m)，且在途中对它威胁程度最小的怪兽的
威胁程度尽可能大。
当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终=0。
输入格式(run.in)
第一行两个数 n,m。
接下来 n 行，每行 m 个数，如果该数为 0，则表示该位置没有怪兽，否则存在怪兽。
数据保证至少存在一个怪兽。
输入格式(run.out)
一个数表示答案。
输入样例
3 4
0 1 1 0
0 0 0 0
1 1 1 0
输出样例
1
数据范围
对于 20%的数据 n=1。
对于 40%的数据 n<=2。
对于 60%的数据 n,m<=10。
对于 80%的数据 n,m<=100。
对于 90%的数据 n,m<=1000。
对于另外 10%的数据 n,m<=1000 且怪兽数量<=100。
思路：
读完题目我以为这是一道DP题
而且DP方程都想好了大半
然而一看时间5000ms
着实吃了一惊
这时间不写搜索简直对不起出题人
对于这种输出最大ans的题
可以写记忆化搜索，但是作为蒟蒻的我代码能力不行
所以写了一个bfs
写完bfs以后又加了一个二分答案
bfs是用来处理每个点的威胁值
就是把所有的怪兽的坐标都记录然后入队
这样处理
二分答案处理ans
每二分出一个答案就进行一遍判定
看这个答案是否可行
可行就记录然后将左边界上调
不行就将右边界下调
指导左右边界交叉
输出最后ans
注意！
记录怪兽的数组必须开大
不然第9个点就wa了
我可是被坑过的人；
来，上代码：
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; struct node {
int x,y,dis;
};
struct node cur; const int dx[]={,-,,,};
const int dy[]={,,,,-}; int l=,r=,ans;
int gx[],gy[],head=;
int n,m,map[][],pd[][]; void bfs()
{
queue<struct node>q;
for(int i=;i<=head;i++) cur.x=gx[i],cur.y=gy[i],cur.dis=i,pd[cur.x][cur.y]=cur.dis,q.push(cur);
while(!q.empty())
{
for(int i=;i<=;i++)
{
cur=q.front();
if(cur.x+dx[i]<=n&&cur.x+dx[i]>&&cur.y+dy[i]>&&cur.y+dy[i]<=m)
{
if(pd[cur.x+dx[i]][cur.y+dy[i]]==)
{
pd[cur.x+dx[i]][cur.y+dy[i]]=cur.dis;
cur.x+=dx[i],cur.y+=dy[i];
map[cur.x][cur.y]=fabs(gx[cur.dis]-cur.x)+fabs(gy[cur.dis]-cur.y);
q.push(cur);
}
}
}
q.pop();
}
} bool check(int now)
{
memset(pd,,sizeof(pd));
queue<struct node>q;
if(map[][]<now) return false;
cur.x=,cur.y=;
pd[][]=;
q.push(cur);
while(!q.empty())
{
for(int i=;i<=;i++)
{
cur=q.front();
if(cur.x+dx[i]<=n&&cur.x+dx[i]>&&cur.y+dy[i]<=m&&cur.y+dy[i]>)
{
cur.x+=dx[i],cur.y+=dy[i];
if(pd[cur.x][cur.y]==&&map[cur.x][cur.y]>=now)
{
if(cur.x==n&&cur.y==m) return true;
pd[cur.x][cur.y]=;
q.push(cur);
}
}
}
q.pop();
}
return false;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d",&map[i][j]);
if(map[i][j]==)
{
head++;
gx[head]=i;
gy[head]=j;
map[i][j]=;
}
}
}
bfs();
while(l<=r)
{
int mid=(l+r)/;
if(check(mid))
{
ans=mid;
l=mid+;
}
else r=mid-;
}
cout<<ans<<endl;
return ;
}