首页 > 其他 > 详细

CF242C King's Path(思维+bfs)

时间:2021-07-20 23:26:54      阅读:4      评论:0      收藏:0      [点我收藏+]

link

思路:

由于It is guaranteed that the total length of all given segments doesn‘t exceed \(10^{5}\).所以暴力的标记每个能够通过的点跑bfs就好了。
注意标记的时候借助\(pair和map\),如果映射到一维的话会爆\(ll\)吧。

代码:

const int maxn=1e5+100;

ll sx,sy,ex,ey,n;
struct node{
	ll x,y,val,step;
};


int nx[8]={-1,-1,-1,0,0,1,1,1};
int ny[8]={-1,0,1,-1,1,-1,0,1};

map<PLL,ll>mp;

int main(){
	sx=read,sy=read,ex=read,ey=read;
	n=read;	
	for(ll i=1;i<=n;i++){
		ll r=read,a=read,b=read;
		for(ll j=a;j<=b;j++){
			mp[{r,j}]=-1;
		}
	}
	queue<PLL>q;
	q.push({sx,sy});
	mp[{sx,sy}]=0;
	while(!q.empty()){
		PLL t=q.front();q.pop();
		if(t.first==ex&&t.second==ey){
			cout<<mp[t]<<"\n";return 0;
		}
		for(int i=0;i<8;i++){
			PLL tmp={t.first+nx[i],t.second+ny[i]};
			if(mp[tmp]==-1&&mp.count(tmp))
				mp[tmp]=mp[t]+1,q.push(tmp);
		}
	}
	cout<<mp[{ex,ey}];
	return 0;
}

CF242C King's Path(思维+bfs)

原文:https://www.cnblogs.com/OvOq/p/15036871.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!