太阳系DISCO

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
//就是bfs，然后遍历所有位置就行了吧，加上步数计数，把那个环看成一个图
//广度优先搜索需要队列，c语言要自己创建队列恶心
typedef struct{
    int bianhao; //所到达星球的编号
    int time_count;// 到达这个位置花费的单位时间
    int chuansong; //到达这个位置所剩余的传送次数
}pos;

#define N (int)200000

pos queue[N];
int queue_front=0;
int queue_end=0;

//判断是否空队列
bool is_empty_queue()
{
    if(queue_front==queue_end)
    {return true;}
    return false;
}

//入队，循环队列
bool queue_push(pos temp)
{
    if(((queue_end+1)%N)==queue_front) //队列满了
    {return false;}
    queue[queue_end]=temp;
    
    queue_end=(queue_end+1)%N;//求余回到队头
    return true;
}

//出队
pos queue_pop()
{
    pos temp=queue[queue_front];
    queue_front=(queue_front+1)%N;
    return temp;
}

//清空队列
void clear_queue(){
    queue_front=0;
    queue_end=0;
}

int n,//行星数量，且 n 为偶数
    k, //技能可使用的最大次数
    a,b,//起点与终点的编号
    x,y;//每次普通移动的距离
int *stars;  //行星环
int min_time;  //到达终点所花的最少时间
int B;  //终点的编号
//bfs遍历
void bfs()
{
    while (!is_empty_queue()) {  //队列不为空时取出队列
        pos temp=queue_pop();

        if (temp.bianhao==b) { //是否到达终点,结束标记
            if(temp.time_count<min_time)  //到达终点的时间是否最少
            {
                min_time=temp.time_count;
            }
            return;
        }

        //往三种操作探索，每次操作均消耗1 个单位时间
        if (stars[(temp.bianhao+x)%n]==0) {     //顺时针移动 x 颗行星
            stars[(temp.bianhao+x)%n]=1;//阻塞这个位置

            //把这个位置加入队列
            pos t={
                .bianhao=(temp.bianhao+x)%n,
                .chuansong=temp.chuansong,
                .time_count=temp.time_count+1
            };
            queue_push(t);    
        }
        if (stars[(temp.bianhao+(n-y))%n]==0) {     //逆时针移动 y 颗行星，相当于顺时针移动(n-y)颗星
            stars[(temp.bianhao+(n-y))%n]=1;//阻塞这个位置

            //把这个位置加入队列
            pos t={
                .bianhao=(temp.bianhao+(n-y))%n,
                .chuansong=temp.chuansong,
                .time_count=temp.time_count+1
            };
            queue_push(t);    
        }
        if(stars[(temp.bianhao+(n/2))%n]==0&&temp.chuansong>=1)  //传送技能，顺时针移动 n/2颗行星,  需要有传送技能才能发动传送
        {
            stars[(temp.bianhao+(n/2))%n]=1;//阻塞这个位置
            //把这个位置加入队列
            pos t={
                .bianhao=(temp.bianhao+(n/2))%n,
                .chuansong=temp.chuansong-1,  //注意传送次数减1
                .time_count=temp.time_count+1
            };
            queue_push(t);
        }
    }
}

int main() {
    
    scanf("%d %d %d %d %d %d",&n,&k,&a,&b,&x,&y);

    min_time=n+1; //初始化最少时间
    //初始化行星地图，0元素不要，数值为0表示这个位置还没有到达过
    stars=malloc(sizeof(int)*(n+1));
    memset(stars,0,sizeof(int)*(n+1));

    //起点进入队列然后开始bfs遍历
    pos start_pos={
        .bianhao=a,
        .time_count=0,
        .chuansong=k
    };
    //入队列
    queue_push(start_pos);
    //阻塞这个位置
    stars[start_pos.bianhao]=1;
    bfs();
    if (min_time>n) {
        printf("-1");  //无法到达终点
    }else {
        printf("%d",min_time);
    }

    return 0;
}