[abc] AtCoder Beginner Contest 241 F - Skate 非单步走bfs

前言

传送门 :

题意

给定一个 N ∗ M ( 1 e 9 ) N *M (1e9) N∗M(1e9)的图,给定起点和终点,选定一个方向冲刺

只有在撞到障碍物的时候才会停下,问最少多少步到终点

思路

本题最大的难点就是,图有点大和 b f s bfs bfs不好操作

我们可以使用 m a p < i n t , p i i > L , R map L,R mapL,R存储障碍物信息

然后对于当前位置,可以使用二分查找,找到可以到达的障碍物位置,然后每次更新位

置即可 , (具体看操作)

由于宏定义了#define x first | y second,所以查看代码的时候需要注意

Mycode

map L,R;
set done;
queue q;
int h,w,n;
int sx,sy,gx,gy;
void solve()
{
	cin>>h>>w>>n;
	cin>>sx>>sy>>gx>>gy;
	for(int i=1;i>u>>v;
		L[u].insert(v);//行上的列
		R[v].insert(u);//列上的行
	}
	
	q.push({0,{sx,sy}});
	while(!q.empty()){
		auto t = q.front();
		q.pop();
		
		auto cost  = t.x;
		auto pos   = t.y;
		
		if(done.find(pos) != done.end())  continue;
		
		done.insert(pos);
		auto px = pos.x;
		auto py = pos.y;
		if(px == gx && py == gy){
			cout