当前位置：首页 > news >正文

牛客周赛54：D.清楚姐姐跳格子（bfs）

news 2025/7/13 23:35:04

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

\,\,\,\,\,\,\,\,\,\,老妪遂递一羊皮卷轴，上面什么都没有，清楚欲问，老妪却缄口不言。
\,\,\,\,\,\,\,\,\,\,清楚性格刚直，放下鼠资，正欲再问，忽觉眼前一花，老妪和店铺却都消失不见，唯卷轴与竹鼠。
\,\,\,\,\,\,\,\,\,\,“怪哉”，清楚回头走，见到地上有一些格子。

\,\,\,\,\,\,\,\,\,\,清楚正在玩跳格子游戏。地上有 nnn 个格子，清楚一开始在 111 号格子，目标是 nnn 号格子。

\,\,\,\,\,\,\,\,\,\,第 iii 个格子上有一个数字 aia_iai ，清楚在这个格子上可以往左右两边选一个方向，然后选择 aia_iai 的一个正整数因子作为长度，进行一次跳跃，但是不可以跳出边界。
\,\,\,\,\,\,\,\,\,\,请问清楚最少跳多少步，就可以到达 nnn 号格子。

输入描述:

          \,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n ( 1≤n≤103 )n\ (\ 1 \leq n \leq 10^3\ )n ( 1≤n≤103 ) 代表格子数量。\,\,\,\,\,\,\,\,\,\,第二行输入 nnn 个整数 a1,a2,…,an ( 1≤ai≤1018 )a_1,a_2,\dots,a_n\ (\ 1 \leq a_i \leq 10^{18}\ )a1,a2,…,an ( 1≤ai≤1018 ) 代表格子上的数字。

输出描述:

          \,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表到达终点需要的最少步数 。

示例1

输入

复制5 2 3 1 5 4

5
2 3 1 5 4

输出

复制2

说明

          \,\,\,\,\,\,\,\,\,\,在 111 号节点 ，选择 a1a_1a1 的因子 111 ，往右跳 111 步，到达 222 号节点。\,\,\,\,\,\,\,\,\,\,在 222 号节点 ，选择 a2a_2a2 的因子 333 ，往右跳 333 步，到达 555 号节点。

做法

直接bfs搜就好了

#include<bits/stdc++.h>
using namespace std;
int vis[1010];
long long a[1010];
int n;
struct ty{int x,cnt;
};
queue<ty> q;
void bfs(){q.push({1,0});while(!q.empty()){ty tmp=q.front();q.pop();if(tmp.x==n){cout<<tmp.cnt;return ;}if(vis[tmp.x]) continue;vis[tmp.x]=1;for(int i=1;i<=n;i++){if(a[tmp.x]%i) continue;if(i+tmp.x<=n&&vis[tmp.x+i]==0){q.push({tmp.x+i,tmp.cnt+1});}if(tmp.x-i>=1&&vis[tmp.x-i]==0){q.push({tmp.x-i,tmp.cnt+1});}}}
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);bfs();
}