题目大意
给你一张nn*mm矩形地图。上面有些点上有敌营。给你起点和终点, 你找出一条最优路径。满足最优路径上的点离敌营的最近最短距离是所有路径最短的。若有多条找路径最短的一条。
分析
通过二分来确定路径离敌营最短距离。然后bfs来验证。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define maxn 1010
#define MAXN 2005
#define MAXM 20000005
#define INF 100000000000000
#define oo 1000000007
using namespace std; typedef long long LL;
struct Point
{
int x,y,dist;
}p[maxn*maxn];
int mid,n,nn,mm,stx,sty,edx,edy;
int vist[maxn][maxn],vistdist[maxn][maxn];
int dirx[]={,-,,};
int diry[]={-,,,};
int max_dist,dist1,dist2;
void bfs1()
{
queue<Point> q;
while(!q.empty())
q.pop();
for(int i=;i<n;i++)
q.push(p[i]);
while(!q.empty())
{
Point tem=q.front();
q.pop(); for(int i=;i<;i++)
{
int newx=tem.x+dirx[i];
int newy=tem.y+diry[i];
if(newx>=&&newx<mm&&newy>=&&newy<nn&&!vist[newx][newy])
{
vist[newx][newy]=;
int newdist=tem.dist+;
vistdist[newx][newy]=newdist;
max_dist=max(max_dist,newdist);
Point pp;
pp.x=newx;
pp.y=newy;
pp.dist=newdist;
q.push(pp);
}
}
}
}
int bfs2()
{
queue<Point> q;
while(!q.empty())
q.pop();
Point pp;
pp.x=stx;
pp.y=sty;
pp.dist=;
q.push(pp);
memset(vist,,sizeof(vist));
if(vistdist[stx][sty]<mid)
return ; while(!q.empty())
{
Point tem=q.front();
q.pop();
if(tem.x==edx&&tem.y==edy)
{
dist1=mid;
dist2=tem.dist;
return ;
}
for(int i=;i<;i++)
{
int xx=tem.x+dirx[i];
int yy=tem.y+diry[i];
if(xx>=&&xx<mm&&yy>=&&yy<nn&&!vist[xx][yy]&&vistdist[xx][yy]>=mid)
{
vist[xx][yy]=;
Point pp;
pp.x=xx;
pp.y=yy;
pp.dist=tem.dist+;
q.push(pp);
} }
}
return ; }
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&n,&mm,&nn);
scanf("%d %d %d %d",&stx,&sty,&edx,&edy);
memset(vist,,sizeof(vist));
for(int i=;i<n;i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
p[i].dist=;
vistdist[p[i].x][p[i].y]=;
vist[p[i].x][p[i].y]=;
}
max_dist=-;
bfs1();
int l=,r=max_dist;
while(l<=r)
{
mid=(l+r)/;
if(bfs2())
l=mid+;
else
r=mid-; }
printf("%d %d\n",dist1,dist2);
}
return ;
}
注意的是队列数组别开小了，还有就是插入队列的时候应该这样写
Point pp;
pp.x=newx;
pp.y=newy;
pp.dist=newdist;
q.push(pp);
如果这样写就会CE
q.push((Point){newx,newy,newdist});