求助&警示后人 关于bfs中标记对搜索效率的影响
查看原帖
求助&警示后人 关于bfs中标记对搜索效率的影响
678087
fangzichang楼主2022/9/29 19:29

rt,今天考到这个题,晚上调对了,但是一个问题还没解决,在这里求助
上bfs

void bfs(int x,int y){
	queue<pii> q;
	q.push({x,y});
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		int xx=u.first,yy=u.second;
//		vis[xx][yy]=1;① 
		for(int i=0;i<4;i++){
			if(a[xx+dx[i]][yy+dy[i]]<a[xx][yy]&&!vis[xx+dx[i]][yy+dy[i]]){
				q.push({xx+dx[i],yy+dy[i]});
//				vis[xx+dx[i]][yy+dy[i]]=1;② 
			}
		}
	}
}

代码应当比较浅显罢,,一开始只写了②处标记,结果WA了
只写①处标记则TLE
中间试图使用手写队列优化得到了RE与MLE,,,解释了我中间一大堆提交
最后突发奇想两个都加跑得飞起来,所以为什么呢,,,,

2022/9/29 19:29
加载中...