P6245 The Climbing Wall S 题解

题目方法

直接 BFS 爆搜。

思路

先找出 $y \le 1000$ 的落脚点，将这个落脚点的位置存入队列中，接着套入 BFS 的模板，判断当前的落脚点是否可以走到第 $i$ 个落脚点，若可以则继续存入队列中（详见代码注释）。

代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
queue<int>a,b,c;//a存x坐标 b存y坐标 c存步数
int ans,f,h;
int x[10010],y[10010],d[10010];
void bfs()
{
	int wx,wy,wz;
	while(!a.empty())
	{
		wx=a.front();
		a.pop();	
		wy=b.front();
		b.pop();	
		wz=c.front();
		c.pop();	//取出x坐标 y坐标 步数
		for(int i=1;i<=f;i++)
		{
			if(d[i])
				continue;//如果已经走过则不再走
			double dx=abs(wx-x[i]),dy=abs(wy-y[i]);
			double p=sqrt(dx*dx+dy*dy);//求出距离
			if(p>1000)
				continue;//如果距离大于1000则不能走这个落脚点
			if(y[i]>=h-1000)
			{
				ans=wz+1;
				return ;
			}//如果能直接到达墙顶则找到了答案 退出BFS
			d[i]=1;//标记这个落脚点已经走过
			a.push(x[i]);	
			b.push(y[i]);
			c.push(wz+1);//存入新的落脚点的x坐标 y坐标 步数
		}
	}
}
int main()
{
     cin>>h>>f;
	 for(int i=1;i<=f;i++)
	 {
		 cin>>x[i]>>y[i];
		 if(y[i]<=1000)
			 a.push(x[i]),b.push(y[i]),c.push(1);//将符合题意的落脚点存入队列中
	 }
	 bfs();
	 cout<<ans;
    return 0;
}