输入输出样例
输入
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;
}