30分,求助
查看原帖
30分,求助
241641
CRISPRCas9楼主2021/4/16 18:49
#include<iostream>
#include<queue>
#define N 210
using namespace std;
const int INF = -1;
int n;
int start;  //起点楼层
int terminal;  //目标楼层
int k[N];  //每层楼的数字
int d[N];  //到各层楼的最短操作数

int bfs()
{
    queue<int> que;
    //初始化
    for(int i = 1; i <= n; i++)
        d[i] = INF;
    //将起点加入队列,并设置为0
    que.push(start);
    d[start] = 0;
    //不断循环直到队列长度为0
    while(que.size())
    {
        //从最前端取出元素
        int p = que.front();
        que.pop();
        //如果已经是终点,则退出
        if(p == terminal)
            break;
        //可以移动的话,加入队列,并确定距离
        for(int i = 1; i <= n; i++)
        {
            int nx1 = p + k[i];
            int nx2 = p - k[i];
            if(nx1 <= n && d[nx1] == INF)
            {
                que.push(nx1);
                d[nx1] = d[p] + 1;
            }
            if(nx2 >= 1 && d[nx2] == INF)
            {
                que.push(nx2);
                d[nx2] = d[p] + 1;
            }
        }
    }
    return d[terminal];
}
int main()
{
    cin >> n >> start >> terminal;
    for(int i = 1; i <= n; i++)
        cin >> k[i];
    int ans = bfs();
    for(int i = 1; i <= n; i++)
        cout << d[i] << " ";
    cout << endl;
    cout << ans;
    return 0;
}
2021/4/16 18:49
加载中...