首页 > 其他分享 >P1135 奇怪的电梯 (双向bfs)

P1135 奇怪的电梯 (双向bfs)

时间:2024-03-27 19:30:20浏览次数:29  
标签:down temp int up bfs vis 电梯 step P1135

输入输出样例

输入 

5 1 5
3 3 1 2 5

输出

3

说明/提示

对于 100%100% 的数据,1≤N≤200,1≤A,B≤N,0≤Ki​≤N。

本题共 1616 个测试点,前 1515 个每个测试点 66 分,最后一个测试点 10 分。

1.重写AC代码:将步数记录在结构体中

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

struct node{
	int u,d,step;
};
node a[210];

int cnt;
int vis[210];
int n,x,bb;
int path[210] = {-1};

bool bfs(int x){
	vis[x] = true;
	path[x] = 0;
	queue<node> q;
	q.push({a[x].u,a[x].d});
	
	while(!q.empty()){
		node temp;
		temp = q.front();
		q.pop();
		
		int up = temp.u;
		int down = temp.d;
		
		if(up != -1 && !vis[up]){
			vis[up] = true;
			a[up].step = temp.step + 1;
			q.push(a[up]);
		}
		if(down != -1 && !vis[down]){
			vis[down] = true;
			a[down].step = temp.step + 1;
			q.push(a[down]);
		}
		if(up == bb || down == bb){
			return true;
		}
	}
	return false;
}
int main()
{
	//要求从a到b 
	scanf("%d%d%d",&n,&x,&bb);
	for(int i=1;i<=n;i++){
		int c;
		scanf("%d",&c);
		a[i].u = c + i;
		a[i].d = i - c;

		if(a[i].u > n || a[i].u < 1) a[i].u = -1;
		if(a[i].d > n || a[i].d < 1) a[i].d = -1;
	} 
	if(bfs(x)) printf("%d",a[bb].step);
	else printf("-1");
	return 0;
}
 

结果:

2.AC代码:单设path数组记录到达每层楼用的步数

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

struct node{
	int u,d,step,id;
};
node a[210];

int cnt;
int vis[210];
int n,x,bb;
int path[210] = {0};

bool bfs(int x){
	vis[x] = true;
	path[x] = 0;
	queue<node> q;
	q.push({a[x].u,a[x].d});
	
	while(!q.empty()){
		node temp;
		temp = q.front();
		q.pop();
		
		int up = temp.u;
		int down = temp.d;
		
		if(up != -1 && !vis[up]){
			vis[up] = true;
			//a[up].step = temp.step + 1;
			 path[up] = path[temp.id] + 1;
			q.push(a[up]);
		}
		if(down != -1 && !vis[down]){
			vis[down] = true;
			//a[down].step = temp.step + 1;
			path[down] = path[temp.id] + 1;
			q.push(a[down]);
		}
		if(up == bb || down == bb){
			return true;
		}
	}
	return false;
}
int main()
{
	//要求从a到b 
	scanf("%d%d%d",&n,&x,&bb);
	for(int i=1;i<=n;i++){
		int c;
		scanf("%d",&c);
		a[i].u = c + i;
		a[i].d = i - c;
		a[i].id = i;
		if(a[i].u > n || a[i].u < 1) a[i].u = -1;
		if(a[i].d > n || a[i].d < 1) a[i].d = -1;
	} 
	//if(bfs(x)) printf("%d",a[bb].step);
	if(bfs(x)) printf("%d",path[bb]);
	else printf("-1");
	return 0;
}
 

结果:

标签:down,temp,int,up,bfs,vis,电梯,step,P1135
From: https://blog.csdn.net/2401_82736456/article/details/137059689

相关文章

  • 洛谷P1443 马的遍历(bfs模版题)
    洛谷P1443马的遍历https://www.luogu.com.cn/problem/P1443一道经典的bfs入门题这里贴上代码//#defineLOCAL1#define_CRT_SECURE_NO_WARNINGS1#include<bits/stdc++.h>//#defineintlonglong#defineendl"\n";usingnamespacestd;constintmaxn=500;intG......
  • 十三 1355. 母亲的牛奶 (BFS)
    1355.母亲的牛奶(BFS)思路:使用BFS搜索所有可能出现的情况,同时保存到used数组,防止重复搜索,最后遍历used数组,因为只求C桶中牛奶,所有先遍历C桶,出现A桶为空立即打印结果并break。importjava.util.*;publicclassMain{privatestaticintA,B,C;privatestatic......
  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......
  • 浅析BFS
    广度优先搜索(BFS)广度优先算法(BFS)又称宽度优先搜索,是指依次将与根节点路径长度(默认每条边长度相同)相同的点遍历,再遍历路径长度加一的点,直到遍历完整个图结束。BFS在树中的应用作用:BFS用于在树中搜索某个特定的数据。方法:从根节点开始搜索,按层遍历整个树。一般使用队......
  • 【BFS】(代码详解)
    全面学习BFS的可以参照以下路径,本文章只附上部分代码的解释作为学习记录共勉(星星眼)原文链接:https://blog.csdn.net/m0_62881629/article/details/125072287给定一个n×mn×m的二维整数数组,用来表示一个迷宫,数组中只包含00或11,其中00表示可以走的路,11表示不可通过......
  • 1.基于搜索的路径规划:BFS、DFS、Dijkstra、A*、JPS
    1.概览可以对比不同算法的小动画 PathFinding.js(qiao.github.io)工作空间规划机器人有不同的形状和大小碰撞检测需要了解机器人的几何形状,耗时且难度大 我们希望将机器人表示为点,只需要把工作空间转换为配置空间C-obstacle,将原始的空间膨胀,这是一次性的C-space......
  • 【力扣】岛屿数量(体会一下dfs和bfs思路的实质)
    题目描述注意,需要求的是岛屿的数量,而不是岛屿的总面积,这道题很考验对dfs思路的理解,而不是简单地套用模版。可以用dfs和bfs两种方法做。深度优先搜索版本首先看代码:classSolution{private:intdir[4][2]={0,1,1,0,-1,0,0,-1};//四个方向voiddfs(ve......
  • 《牛客》-E魔法之森的蘑菇(经典BFS变种)
    思路:由于某些固定方向的情况,我们将到达该点的粒度划分成从那个方向的到达该点,及基础bfs为每个点可以到达一次,变成没个点可以到达四次(四个方向)用一个三维数组进行标记vis[N][N][4],其余细节看下方ACcodeACcode:#include<bits/stdc++.h>usingnamespacestd;#defineendl......
  • BFS记忆化搜索---标记
    迷宫(洛谷)题目描述给定一个\(N\timesM\)方格的迷宫,迷宫里有\(T\)处障碍,障碍处不可通过。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。输入格式第......
  • 刷题日记——干碎那个BFS!(含国科大机试2021)
    例题小引——迷宫问题问题描述:迷宫由n行m列的单元格组成(n,m都小于等于50),每个单元格要么是空地,要么是障碍物。现请你找到一条从起点到终点的最短路径长度。分析——(迷宫问题BFS解法)使用BFS算法,进行广度优先遍历,总体思路是访问一个结点,就把相邻的结点入队,然后下一个访......