题目大意
小B目前正在玩一个非常无聊的游戏，你从一个基地开始你的角色并试图偷走对手的水晶。然而，当他试图返回城市时，他意识到这个角色已经这么做了。生成在地图上。
n
n
怪物。
现在考虑地图是一个二维平面，所有怪物和角色都位于这个二维平面上的点。请帮小B算一算。从当前角色位置开始，你必须消灭至少一些怪物才能让他返回基地（坐标原点）。
注意：小b控制的角色只能向平行于坐标轴的方向（东、西、南、北）移动，并且每次必须移动整数距离。
数据范围
1
n
50000
1n50000
1n50000
1
X
,
y
1000
1x,y1000
1x,y1000
输入格式
第一行包含三个整数。
n
n
n 和字符的初始位置
（
X
,
y
）
(x,y)
(x,y)。
下一个
n
n
n行，每行包含奇怪的位置坐标
（
X
,
y
）
(x,y)
(x,y)。
输出格式
表示要消灭的怪物的最小数量的数字。
输入样本
7 6 3
6 2
5 2
4 3
21
7 3
5 4
6 4
输出样本
1
基本思路
了解你的起点和终点，并逐步扩展你的问题。
乙
F
s
广度FS
BF的特点。
但很简单
乙
F
s
广度FS
bfs只管理部分层数，但不管理通过的怪物数量。但问题是至少要经过怪物，所以绕道是非常有必要的，而且通常
乙
F
s
广度FS
在bfs中，怪物点可能会先扩张，这就违反了这个原则。
所以我们引入了一些新东西：双端队列。
d
e
q
你
e
出库
德库。顾名思义，元素可以进入和离开团队的开头和结尾。因此，没有怪物的积分可以从队伍的开头进入，有怪物的积分可以从队伍的末尾进入，即使想要取积分也必须从队伍的开头取。这样可以让你在不消灭应该消灭的怪物的情况下，尽可能的避开怪物。
核心代码
#includebits/stdc++.h
使用命名空间标准。
typedef 无符号长长ull；
常量int N=1e3+10;
结构节点{
int x,y,cnt；
};
int n,sx,sy,w[4][2]={{0,1},{1,0},{0,-1},{-1,0}},ans=0x3f3f3f3f;
布尔v[N][N],a[N][N];
德克诺德库；
内联int bfs(){
q.push_back({sx,sy,0});
v[sx][sy]=真；
while(!q.empty()){
节点u=q.front();
q.pop_front();
if(u.x==0u.y==0)
return u.cnt;//到达终点
for(int i=0;i4;i++){
int xx=u.x+w[i][0],yy=u.y+w[i][1];
if(xx0||xx=N||yy0||yy=N) 继续；
if(v[xx][yy]==true) 继续；
if(a[xx][yy]==true)
q.push_back({xx,yy,u.cnt+1});
除此之外
q.push_front({xx,yy,u.cnt});
v[xx][yy]=真；
}
}
}
int main(){
ios:sync_with_stdio(假);
信都士；
for(int i=1,x,y;i=n;i++){
辛西；
a[x][y]=真；
}
coutbfs();
返回0。
}
以上#[SSL 1823]消灭怪物（非传统BFS）相关内容仅供大家参考。相关信息请参见官方公告。
原创文章，作者：CSDN，如若转载，请注明出处：https://www.sudun.com/ask/93006.html
