题意分析

玩家从格子$1$出发，每次顺时针跳跃固定长度$K$，目标是到达格子$Z$。路径上的所有格子（包括起点和终点）不能有障碍物。需要找到满足条件的最小$K$值。

解题思路

1. 问题建模：

   • 每次跳跃$K$步相当于在环上按固定步长移动，路径为$1 \rightarrow 1+K \rightarrow 1+2K \rightarrow \dots$（模$N$处理）。
   • 对于每个可能的$K$，模拟跳跃过程，检查是否能到达$Z$且路径上无障碍物。

2. 算法选择：

   • 暴力枚举：从小到大枚举$K$（$1 \leq K \leq N$），对每个$K$使用广度优先搜索（BFS）模拟跳跃过程。
   • 终止条件：找到第一个能到达$Z$的$K$，即为最小解。

3. 关键处理：

   • 环的处理：当跳跃后的位置超过$N$时，通过取模运算转换为环上的位置（注意处理整除时的特殊情况，如$N=5$，$K=5$时，$1+5=6$，取模后为$1$）。
   • 障碍物判断：使用布尔数组记录障碍物位置，跳跃时检查目标格子是否被阻挡。

代码解释

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

int main() {
    int N, Z, M; // 注意变量名与题意对应，原代码中m应为Z，z应为M
    cin >> N >> Z >> M; // 输入格子数N、目标Z、障碍物数量M
    
    vector<bool> blocked(N + 1, false); // blocked[x]为true表示格子x有障碍物
    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;
        blocked[x] = true;
    }
    
    // 起点或终点有障碍物，直接无解
    if (blocked[1] || blocked[Z]) {
        cout << -1 << endl;
        return 0;
    }
    
    // 从小到大枚举K
    for (int K = 1; K <= N; ++K) {
        vector<bool> visited(N + 1, false); // 记录访问过的格子
        queue<int> q;
        q.push(1);
        visited[1] = true;
        bool found = false; // 是否到达目标
        
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            
            if (current == Z) { // 到达目标
                found = true;
                break;
            }
            
            // 计算下一个位置：current + K，处理环的情况
            int next = current + K;
            if (next > N) {
                next = next % N;
                if (next == 0) next = N; // 处理整除情况，如N=5, K=5时，1+5=6→6%5=1，但实际应为5
            }
            
            // 检查下一个位置是否可访问
            if (!visited[next] && !blocked[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
        
        if (found) { // 找到最小的K
            cout << K << endl;
            return 0;
        }
    }
    
    // 所有K都不满足条件
    cout << -1 << endl;
    return 0;
}

注意事项

1. 变量名修正：

   • 原代码中输入变量名存在混淆（如将$Z$误写为$m$，$M$误写为$z$），已修正为符合题意的命名。

2. 环的取模处理：

   • 当current + K > N时，直接取模可能导致错误（如$N=5$，$K=5$，1+5=6，取模为$1$，但实际应为$5$）。需特殊处理整除情况，确保结果在$1$到$N$之间。

3. 障碍物检查：

   • 起点$1$和终点$Z$保证无障碍物，但代码中仍进行检查以应对输入异常（题目已保证，可省略，但增强鲁棒性）。

4. 枚举顺序：

   • 按$K$从小到大枚举，一旦找到符合条件的解立即输出，确保得到最小$K$。

复杂度分析

• 时间复杂度：$O(N^2)$，每个$K$最多遍历$N$个格子，总共有$N$个可能的$K$值。
• 空间复杂度：$O(N)$，用于存储障碍物数组和访问标记数组。

该算法适用于题目给定的数据范围（$N \leq 1000$），能够在合理时间内找到最优解。