太阳系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;
}

package main

import (
	"bufio"
	"fmt"
	"os"
)

/* 
    BFS
    visited[pos][tp] 表示在位置 pos，使用 tp 次传送的状态是否访问过
	tp 只有 0 和 1 两种状态（因为用两次等于没用）
    queue := []State
 */

type State struct {
	pos   int // 当前位置 (0 ~ n-1)
	steps int // 已用步数
	tp    int // 是否使用过传送: 0 或 1
}

func minSteps(n, k, a, b, x, y int) int {
	a-- // 转为 0-indexed
	b-- // 转为 0-indexed

	if a == b {
		return 0
	}

	// visited[pos][tp] 表示在位置 pos，使用 tp 次传送的状态是否访问过
	// tp 只有 0 和 1 两种状态（因为用两次等于没用）
	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, 2) // tp: 0 或 1
	}

	// BFS 队列
	queue := []State{{a, 0, 0}}
	visited[a][0] = true

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:] // 出队

		nextSteps := cur.steps + 1

		// 1. 顺时针移动 x 步
		p1 := (cur.pos + x) % n
		if !visited[p1][cur.tp] {
			if p1 == b {
				return nextSteps
			}
			visited[p1][cur.tp] = true
			queue = append(queue, State{p1, nextSteps, cur.tp})
		}

		// 2. 逆时针移动 y 步
		p2 := (cur.pos - y + n) % n // +n 防止负数
		if !visited[p2][cur.tp] {
			if p2 == b {
				return nextSteps
			}
			visited[p2][cur.tp] = true
			queue = append(queue, State{p2, nextSteps, cur.tp})
		}

		// 3. 使用传送技能（跳到对面）
		if cur.tp == 0 && k >= 1 { // 还没用过，且 k >= 1
			p3 := (cur.pos + n/2) % n
			if !visited[p3][1] {
				if p3 == b {
					return nextSteps
				}
				visited[p3][1] = true
				queue = append(queue, State{p3, nextSteps, 1})
			}
		}
	}

	return -1
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, k, a, b, x, y int
	_, err := fmt.Fscan(reader, &n, &k, &a, &b, &x, &y)
	if err != nil {
		panic(err)
	}

	result := minSteps(n, k, a, b, x, y)
	fmt.Println(result)
}

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int safe_mod(int a, int b) {
    return (a % b + b) % b;
}

int main() {
    int n, k, a, b, x, y;
    cin >> n >> k >> a >> b >> x >> y;
    
    // 定义移动方式
    vector<int> moves = {+x, -y};
    if (k > 0) {
        moves.push_back(+n/2);  // 只有k>0时才允许使用第三种移动
    }
    
    queue<int> q;
    vector<bool> visited(n, false);
    
    if(a == b) {
        cout << 0 << endl;
        return 0;
    }
    
    q.push(a);
    visited[a] = true;
    int steps = 0;
    bool found = false;
    
    while(!q.empty() && steps <= k + n) {  // 合理设置上限
        int sz = q.size();
        while(sz--) {
            int current = q.front();
            q.pop();
            
            for(int move : moves) {
                int next = safe_mod(current + move, n);
                
                if(next == b) {
                    cout << steps + 1 << endl;
                    return 0;
                }
                
                if(!visited[next]) {
                    visited[next] = true;
                    q.push(next);
                }
            }
        }
        steps++;
    }
    
    cout << -1 << endl;
    return 0;
}

public static int solve(int size, int k, int start, int end, int shun, int ni) {
        //记录该点是否访问过，0表示未访问，1表示访问过
        int[] nums = new int[size + 1];
        //广搜
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        int step = 0;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                int node = queue.remove();
                //该点访问过，直接跳过
                if (nums[node] == 1) {
                    continue;
                } else {
                    //该点之前没有访问过，现在访问了，置为1
                    nums[node] = 1;
                }
                //判断是否为终点
                if (node == end) {
                    return step;
                } else {
                    //访问顺时针能到的行星
                    queue.add((node + shun) % size);
                    //访问逆时针能到的行星
                    queue.add((node - ni) == 0 ? size : (node - ni + size) % size);

                    //如果还有传输次数，并且传送目标行星没有被访问过，访问传送能到达的行星
                    if (k > 0 && nums[(node + size / 2) % size] != 1) {
                        queue.add((node + size / 2) % size);
                        k--;
                    }
                }
            }
            //每个行星能访问到的其他3个行星入队后，用时加1
            step++;
        }
        //访问不到，返回-1
        return -1;
    }

from collections import deque

def min_steps(n, k, a, b, x, y):
    a -= 1
    b -= 1

    if a == b:
        return 0

    visited = [[False]*2 for _ in range(n)]
    q = deque()
    q.append((a, 0, 0))  # (当前位置, 步数, teleport_used (0&nbs***bsp;1))
    visited[a][0] = True

    while q:
        pos, steps, tp = q.popleft()

        # 顺时针 x
        p1 = (pos + x) % n
        if not visited[p1][tp]:
            if p1 == b:
                return steps + 1
            visited[p1][tp] = True
            q.append((p1, steps + 1, tp))

        # 逆时针 y
        p2 = (pos - y + n) % n
        if not visited[p2][tp]:
            if p2 == b:
                return steps + 1
            visited[p2][tp] = True
            q.append((p2, steps + 1, tp))

        # 传送，两次及以上就没有意义
        if tp == 0 and k >= 1:
            p3 = (pos + n // 2) % n
            if not visited[p3][1]:
                if p3 == b:
                    return steps + 1
                visited[p3][1] = True
                q.append((p3, steps + 1, 1))

    return -1

# 输入读取
n, k, a, b, x, y = map(int, input().split())
print(min_steps(n, k, a, b, x, y))