【一】LZ信息营-算法课程体系与题目库清单

📊 课程体系总览表

📝 各课程题目库详细整理

【课程01】理解递归函数

核心概念：递归三要素、记忆化递归、分治思想

【课程02】时间复杂度与排序

核心概念：复杂度分析、排序算法比较、自定义排序

【课程03】STL库的应用

核心概念：STL容器选择、算法函数使用、性能分析

【课程04】网格寻路与BFS

核心概念：BFS模板、状态表示、路径记录

【课程05】图论与最短路算法

核心概念：Dijkstra、负环检测、差分约束

【课程06】听说大家喜欢数学题

核心概念：矩阵快速幂、逆元、扩展欧几里得

【课程07】神奇的树状数组

核心概念：BIT单点更新区间查询、差分、逆序对

【课程08】听说大家都学过贪心

核心概念：线段覆盖、排序贪心、后悔贪心

【课程09】二分枚举与按位枚举

核心概念：二分答案、按位枚举、最大化最小值

【课程10】背包九讲

核心概念：01背包、完全背包、多重背包、分组背包

【课程11】暴力枚举的艺术

核心概念：回溯、剪枝、状态压缩、双向搜索

【课程12】经典动态规划问题

核心概念：线性DP、环形处理、股票问题系列

【课程13】区间统计问题研究

核心概念：线段树、单调队列、离散化、逆序对

【课程14】筛法只能求质数？

核心概念：欧拉筛、约数个数、约数和、欧拉函数

【课程15】数论分块

核心概念：整除分块、下取整求和、公式推导

【课程16】贡献思维和单调栈

核心概念：单调栈、贡献法、子数组统计

【课程17】如何设计你的状态

核心概念：状态设计、状态压缩、多维DP

【课程18】尺取法和双指针

核心概念：滑动窗口、同向双指针、相向双指针

【课程19】神奇的根号算法

核心概念：根号分治、莫队算法、分块思想

【课程20】前缀和优化技巧

核心概念：前缀和、哈希表、差分数组

【课程21】生成树与并查集

核心概念：Kruskal、并查集、最小生成树

🎯 考核重点与备考策略

基础必考模块（60分）

1. 递归与搜索（课程01、04）：DFS/BFS模板

2. 排序与STL（课程02、03）：sort、容器使用

3. 基础DP（课程12、17）：线性DP、状态设计

4. 贪心与双指针（课程08、18）：经典贪心、滑动窗口

5. 数据结构基础（课程07）：树状数组基本操作

核心提高模块（30分）

1. 动态规划进阶（课程10）：背包九讲

2. 图论算法（课程05）：最短路、生成树

3. 高级数据结构（课程13）：线段树、单调队列

4. 数学基础（课程06、14）：快速幂、筛法

高级挑战模块（10分）

1. 数论与分块（课程15、19）：数论分块、根号算法

2. 贡献思维（课程16）：单调栈、贡献法

3. 前缀优化（课程20）：前缀和技巧

📚 备考建议

第一阶段：基础巩固（1-2周）

• 完成课程01-04所有题目，掌握递归和BFS

• 掌握课程02-03的STL和排序

• 完成课程07的树状数组基础题

第二阶段：核心提升（2-3周）

• 完成课程08、12、17、18的经典算法

• 掌握课程05的图论基础

• 完成课程10的背包问题

第三阶段：高级突破（1-2周）

• 挑战课程13、14、16、20

• 尝试课程15、19的难题

• 综合练习，提高解题速度

第四阶段：模拟冲刺（1周）

• 每日一套模拟题

• 时间控制训练（3小时/套）

• 错题回顾，查漏补缺

✅ 快速查找表（按算法类型）

最后提醒：信息营选拔考察综合能力，不仅要掌握算法，还要能灵活运用。建议按照课程顺序循序渐进，打好基础后再挑战难题。每道题目都要理解透彻，做到举一反三。

预祝各位同学在信息营选拔中取得优异成绩！ 🚀

【二】LZ信息营-选拔考核全方位复习指南

📚 完整课程体系与算法分类

算法分类体系

┌─ 基础算法 (30%)
│  ├─ 递归与搜索 (课程01, 04)
│  ├─ 排序与STL (课程02, 03)
│  └─ 时间复杂度分析
│
├─ 核心算法 (40%)
│  ├─ 动态规划 (课程10, 12, 17)
│  ├─ 贪心与双指针 (课程08, 18)
│  ├─ 数据结构基础 (课程07)
│  └─ 图论基础 (课程05)
│
└─ 高级算法 (30%)
   ├─ 高级数据结构 (课程13)
   ├─ 数学与数论 (课程06, 14, 15)
   ├─ 贡献思维 (课程16)
   ├─ 优化技巧 (课程20)
   └─ 根号算法 (课程19)

🚀 核心算法模板库（使用i64）

一、递归与搜索模块

1.1 归三要素模板

​x
// ==================== 递归算法系列 ====================

/************************************************************************
 * 1. 阶乘计算（递归基础）
 * 问题：计算n的阶乘 n! = 1×2×...×n
 * 递归三要素：
 *   1. 定义：factorial(n) 计算n的阶乘
 *   2. 边界：n <= 1 时返回1
 *   3. 递推：factorial(n) = n × factorial(n-1)
 * 时间复杂度：O(n)，空间复杂度：O(n)（递归栈）
 ***********************************************************************/
i64 factorial(i64 n) {
    // 边界条件（递归出口）
    if (n <= 1) return 1;
    
    // 递推关系（递归调用）
    return n * factorial(n - 1);
}

// 阶乘的迭代版本（避免栈溢出）
i64 factorial_iterative(i64 n) {
    i64 result = 1;
    for (i64 i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}


/************************************************************************
 * 2. 斐波那契数列 (LS1209)
 * 问题：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
 * 递归三要素：
 *   1. 定义：fibonacci(n) 计算第n项
 *   2. 边界：n <= 1 时返回n
 *   3. 递推：fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
 * 注意：朴素递归时间复杂度O(2^n)，需要记忆化优化
 ***********************************************************************/

// 朴素递归（指数复杂度，不推荐）
i64 fibonacci_naive(i64 n) {
    if (n <= 1) return n;
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2);
}

// 记忆化递归（自顶向下）
i64 fibonacci_memo_helper(i64 n, vector<i64>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // 记忆化剪枝
    
    memo[n] = fibonacci_memo_helper(n - 1, memo) + 
              fibonacci_memo_helper(n - 2, memo);
    return memo[n];
}

i64 fibonacci_memo(i64 n) {
    vector<i64> memo(n + 1, -1);
    return fibonacci_memo_helper(n, memo);
}

// 迭代版本（自底向上，推荐）
i64 fibonacci_iterative(i64 n) {
    if (n <= 1) return n;
    
    i64 prev2 = 0;  // F(0)
    i64 prev1 = 1;  // F(1)
    
    for (i64 i = 2; i <= n; i++) {
        i64 current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}

// 矩阵快速幂（对数复杂度）
i64 fibonacci_matrix(i64 n) {
    if (n <= 1) return n;
    
    // 使用矩阵快速幂
    auto multiply = [](vector<vector<i64>> a, vector<vector<i64>> b) {
        vector<vector<i64>> result(2, vector<i64>(2, 0));
        for (i64 i = 0; i < 2; i++) {
            for (i64 j = 0; j < 2; j++) {
                for (i64 k = 0; k < 2; k++) {
                    result[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return result;
    };
    
    vector<vector<i64>> base = {{1, 1}, {1, 0}};
    vector<vector<i64>> result = {{1, 0}, {0, 1}};  // 单位矩阵
    
    i64 power = n - 1;
    while (power > 0) {
        if (power & 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        power >>= 1;
    }
    
    return result[0][0];
}


/************************************************************************
 * 3. 汉诺塔问题 (LS1028)
 * 问题：将n个盘子从A柱移动到C柱，B柱作为辅助
 * 规则：1. 每次只能移动一个盘子 2. 大盘不能在小盘上
 * 递归三要素：
 *   1. 定义：hanoi(n, from, to, aux) 移动n个盘子
 *   2. 边界：n == 1时直接移动
 *   3. 递推：hanoi(n) = hanoi(n-1) + 移动第n个 + hanoi(n-1)
 * 时间复杂度：O(2^n)，空间复杂度：O(n)
 ***********************************************************************/
void hanoi(i64 n, char from, char to, char aux) {
    // 边界条件：只有一个盘子
    if (n == 1) {
        cout << from << " -> " << to << "\n";
        return;
    }
    
    // 递推关系：
    // 1. 将n-1个盘子从from移到aux（借助to）
    hanoi(n - 1, from, aux, to);
    
    // 2. 移动第n个盘子（最大的）
    cout << from << " -> " << to << "\n";
    
    // 3. 将n-1个盘子从aux移到to（借助from）
    hanoi(n - 1, aux, to, from);
}

// 汉诺塔步数计算（不输出具体步骤）
i64 hanoi_steps(i64 n) {
    if (n == 1) return 1;
    return 2 * hanoi_steps(n - 1) + 1;
}

// 汉诺塔迭代解法（模拟递归栈）
void hanoi_iterative(i64 n, char from, char to, char aux) {
    struct State {
        i64 n;
        char from, to, aux;
        bool move_direct;  // 是否需要直接移动
    };
    
    stack<State> stk;
    stk.push({n, from, to, aux, false});
    
    while (!stk.empty()) {
        State current = stk.top();
        stk.pop();
        
        if (current.n == 1) {
            cout << current.from << " -> " << current.to << "\n";
        } else {
            // 注意入栈顺序与递归调用相反
            if (!current.move_direct) {
                // 对应：hanoi(n-1, aux, to, from)
                stk.push({current.n - 1, current.aux, current.to, current.from, false});
                // 对应：移动第n个
                stk.push({1, current.from, current.to, current.aux, false});
                // 对应：hanoi(n-1, from, aux, to)
                stk.push({current.n - 1, current.from, current.aux, current.to, false});
            }
        }
    }
}


/************************************************************************
 * 4. 约瑟夫环问题 (NC22227)
 * 问题：n个人围成一圈，从0开始报数，报到m-1的人出列，求最后剩下的人编号
 * 递归三要素：
 *   1. 定义：josephus(n, m) 返回n个人，报数到m-1时的幸存者编号
 *   2. 边界：n == 1时返回0（只剩一个人）
 *   3. 递推：josephus(n, m) = (josephus(n-1, m) + m) % n
 * 时间复杂度：O(n)，空间复杂度：O(n)
 ***********************************************************************/
i64 josephus(i64 n, i64 m) {
    // 边界条件：只剩一个人，编号0
    if (n == 1) return 0;
    
    // 递推公式
    return (josephus(n - 1, m) + m) % n;
}

// 约瑟夫环迭代版本（避免递归栈溢出）
i64 josephus_iterative(i64 n, i64 m) {
    i64 result = 0;  // n=1时的结果
    
    // 从2个人开始递推
    for (i64 i = 2; i <= n; i++) {
        result = (result + m) % i;
    }
    
    return result;
}

// 约瑟夫环模拟（暴力验证）
i64 josephus_simulation(i64 n, i64 m) {
    vector<bool> alive(n, true);
    i64 current = 0;
    i64 count = n;
    
    while (count > 1) {
        // 数m-1个人
        for (i64 i = 0; i < m - 1; i++) {
            do {
                current = (current + 1) % n;
            } while (!alive[current]);
        }
        
        // 淘汰当前人
        alive[current] = false;
        count--;
        
        // 找到下一个活着的人
        do {
            current = (current + 1) % n;
        } while (!alive[current]);
    }
    
    // 找到唯一幸存者
    for (i64 i = 0; i < n; i++) {
        if (alive[i]) return i;
    }
    return -1;  // 不应该到达这里
}


/************************************************************************
 * 5. 快速幂递归 (LS1023)
 * 问题：计算a^b，高效实现
 * 递归三要素：
 *   1. 定义：fast_pow(a, b) 计算a的b次方
 *   2. 边界：b == 0时返回1
 *   3. 递推：a^b = (a^(b/2))² 或 a × a^(b-1)
 * 时间复杂度：O(logb)，空间复杂度：O(logb)
 ***********************************************************************/
i64 fast_pow_recursive(i64 a, i64 b) {
    // 边界条件
    if (b == 0) return 1;
    
    // 递推关系
    if (b % 2 == 0) {
        // b是偶数：a^b = (a^(b/2))²
        i64 half = fast_pow_recursive(a, b / 2);
        return half * half;
    } else {
        // b是奇数：a^b = a × a^(b-1)
        return a * fast_pow_recursive(a, b - 1);
    }
}

// 快速幂迭代版本（位运算）
i64 fast_pow_iterative(i64 a, i64 b) {
    i64 result = 1;
    
    while (b > 0) {
        if (b & 1) {  // b是奇数
            result *= a;
        }
        a *= a;      // a平方
        b >>= 1;     // b除以2
    }
    
    return result;
}

// 带模运算的快速幂
i64 fast_pow_mod(i64 a, i64 b, i64 mod) {
    i64 result = 1;
    a %= mod;  // 防止溢出
    
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    
    return result;
}


/************************************************************************
 * 6. 全排列问题
 * 问题：生成数组的所有排列
 * 递归三要素：
 *   1. 定义：permute(nums, start) 生成从start开始的排列
 *   2. 边界：start == n时输出排列
 *   3. 递推：交换每个元素到start位置，递归生成后续排列
 * 时间复杂度：O(n!)，空间复杂度：O(n)
 ***********************************************************************/
void permute_recursive(vector<i64>& nums, i64 start, vector<vector<i64>>& result) {
    // 边界条件：到达末尾，保存当前排列
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    // 递推：将每个元素交换到当前位置，递归生成后续排列
    for (i64 i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);          // 选择当前元素
        permute_recursive(nums, start + 1, result);  // 递归生成后续
        swap(nums[start], nums[i]);          // 回溯，恢复原状
    }
}

vector<vector<i64>> permute(vector<i64>& nums) {
    vector<vector<i64>> result;
    permute_recursive(nums, 0, result);
    return result;
}

// 使用next_permutation生成全排列（STL方法）
vector<vector<i64>> permute_stl(vector<i64> nums) {
    vector<vector<i64>> result;
    
    // 先排序，确保生成所有排列
    sort(nums.begin(), nums.end());
    
    do {
        result.push_back(nums);
    } while (next_permutation(nums.begin(), nums.end()));
    
    return result;
}


/************************************************************************
 * 7. 组合问题
 * 问题：从n个元素中选择k个的所有组合
 * 递归三要素：
 *   1. 定义：combine(n, k, start, path) 生成组合
 *   2. 边界：path长度等于k时保存组合
 *   3. 递推：选择或不选择当前元素
 * 时间复杂度：O(C(n,k))，空间复杂度：O(k)
 ***********************************************************************/
void combine_recursive(i64 n, i64 k, i64 start, vector<i64>& path, vector<vector<i64>>& result) {
    // 边界条件：组合长度达到k
    if (path.size() == k) {
        result.push_back(path);
        return;
    }
    
    // 递推：从start开始选择元素
    for (i64 i = start; i <= n; i++) {
        path.push_back(i);                          // 选择当前元素
        combine_recursive(n, k, i + 1, path, result); // 递归选择后续
        path.pop_back();                            // 回溯，不选择当前元素
    }
}

vector<vector<i64>> combine(i64 n, i64 k) {
    vector<vector<i64>> result;
    vector<i64> path;
    combine_recursive(n, k, 1, path, result);
    return result;
}

// 组合数计算：C(n,k) = C(n-1,k-1) + C(n-1,k)
i64 combination_number(i64 n, i64 k) {
    if (k == 0 || k == n) return 1;
    return combination_number(n - 1, k - 1) + combination_number(n - 1, k);
}

// 组合数记忆化版本
i64 combination_number_memo(i64 n, i64 k, vector<vector<i64>>& memo) {
    if (k == 0 || k == n) return 1;
    if (memo[n][k] != -1) return memo[n][k];
    
    memo[n][k] = combination_number_memo(n - 1, k - 1, memo) +
                 combination_number_memo(n - 1, k, memo);
    return memo[n][k];
}


/************************************************************************
 * 8. 二叉树遍历（递归基础）
 * 问题：二叉树的先序、中序、后序遍历
 * 递归三要素：
 *   1. 定义：traverse(node) 遍历以node为根的子树
 *   2. 边界：node == nullptr时返回
 *   3. 递推：根据遍历顺序递归左右子树
 ***********************************************************************/
struct TreeNode {
    i64 val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(i64 x) : val(x), left(nullptr), right(nullptr) {}
};

// 先序遍历：根 → 左 → 右
void preorder_traversal(TreeNode* root, vector<i64>& result) {
    if (!root) return;  // 边界条件
    
    result.push_back(root->val);               // 访问根节点
    preorder_traversal(root->left, result);    // 遍历左子树
    preorder_traversal(root->right, result);   // 遍历右子树
}

// 中序遍历：左 → 根 → 右
void inorder_traversal(TreeNode* root, vector<i64>& result) {
    if (!root) return;
    
    inorder_traversal(root->left, result);     // 遍历左子树
    result.push_back(root->val);               // 访问根节点
    inorder_traversal(root->right, result);    // 遍历右子树
}

// 后序遍历：左 → 右 → 根
void postorder_traversal(TreeNode* root, vector<i64>& result) {
    if (!root) return;
    
    postorder_traversal(root->left, result);   // 遍历左子树
    postorder_traversal(root->right, result);  // 遍历右子树
    result.push_back(root->val);               // 访问根节点
}


/************************************************************************
 * 9. 最大公约数（欧几里得算法）
 * 问题：计算两个数的最大公约数
 * 递归三要素：
 *   1. 定义：gcd(a, b) 计算a和b的最大公约数
 *   2. 边界：b == 0时返回a
 *   3. 递推：gcd(a, b) = gcd(b, a % b)
 * 时间复杂度：O(log(min(a,b)))，空间复杂度：O(log(min(a,b)))
 ***********************************************************************/
i64 gcd_recursive(i64 a, i64 b) {
    // 边界条件
    if (b == 0) return a;
    
    // 递推关系
    return gcd_recursive(b, a % b);
}

// 迭代版本
i64 gcd_iterative(i64 a, i64 b) {
    while (b != 0) {
        i64 temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 最小公倍数
i64 lcm(i64 a, i64 b) {
    return a / gcd_iterative(a, b) * b;  // 先除后乘防止溢出
}


/************************************************************************
 * 10. 分治算法：归并排序
 * 问题：使用分治思想排序数组
 * 递归三要素：
 *   1. 定义：merge_sort(arr, left, right) 排序arr[left..right]
 *   2. 边界：left >= right时返回（只有一个或零个元素）
 *   3. 递推：分为两半分别排序，然后合并
 * 时间复杂度：O(nlogn)，空间复杂度：O(n)
 ***********************************************************************/
void merge(vector<i64>& arr, i64 left, i64 mid, i64 right) {
    vector<i64> temp(right - left + 1);
    i64 i = left, j = mid + 1, k = 0;
    
    // 合并两个有序数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 复制剩余元素
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 复制回原数组
    for (i64 idx = 0; idx < k; idx++) {
        arr[left + idx] = temp[idx];
    }
}

void merge_sort(vector<i64>& arr, i64 left, i64 right) {
    // 边界条件
    if (left >= right) return;
    
    // 递推关系：分治
    i64 mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);      // 排序左半部分
    merge_sort(arr, mid + 1, right); // 排序右半部分
    merge(arr, left, mid, right);    // 合并两个有序部分
}


/************************************************************************
 * 11. 分治算法：快速排序
 * 问题：使用分治思想排序数组
 * 递归三要素：
 *   1. 定义：quick_sort(arr, left, right) 排序arr[left..right]
 *   2. 边界：left >= right时返回
 *   3. 递推：选择基准，划分数组，递归排序
 * 时间复杂度：平均O(nlogn)，最坏O(n²)，空间复杂度：O(logn)
 ***********************************************************************/
i64 partition(vector<i64>& arr, i64 left, i64 right) {
    // 选择最后一个元素作为基准
    i64 pivot = arr[right];
    i64 i = left - 1;  // 小于基准的元素的边界
    
    for (i64 j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    // 将基准放到正确位置
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

void quick_sort(vector<i64>& arr, i64 left, i64 right) {
    // 边界条件
    if (left >= right) return;
    
    // 递推关系：分治
    i64 pivot_idx = partition(arr, left, right);  // 划分
    quick_sort(arr, left, pivot_idx - 1);         // 排序左半部分
    quick_sort(arr, pivot_idx + 1, right);        // 排序右半部分
}


/************************************************************************
 * 12. 递归转迭代通用模板
 * 使用显式栈模拟递归调用
 ***********************************************************************/
struct RecursiveState {
    i64 n;
    i64 stage;  // 记录递归阶段
    // 其他参数...
};

void recursive_to_iterative_example(i64 n) {
    stack<RecursiveState> stk;
    stk.push({n, 0});  // 初始状态
    
    while (!stk.empty()) {
        RecursiveState& current = stk.top();
        
        switch (current.stage) {
            case 0:  // 相当于递归函数开始
                if (current.n <= 1) {
                    // 相当于边界条件
                    // 处理结果...
                    stk.pop();
                } else {
                    current.stage = 1;
                    stk.push({current.n - 1, 0});  // 相当于递归调用
                }
                break;
                
            case 1:  // 第一次递归调用返回后
                // 处理第一次递归的结果...
                current.stage = 2;
                stk.push({current.n - 2, 0});  // 第二次递归调用
                break;
                
            case 2:  // 第二次递归调用返回后
                // 处理结果并合并...
                stk.pop();  // 当前调用结束
                break;
        }
    }
}

📊 递归三要素总结

📊 常见递归问题分类

📊 递归复杂度分析

📊 递归优化技术

📊 递归 vs 迭代对比

📊 递归常见错误与规避

📊 关联题目索引

【递归核心要点】

【学习建议】

1. 理解原理：掌握递归的数学基础（数学归纳法）

2. 从简单开始：先实现阶乘、斐波那契等简单递归

3. 画递归树：帮助理解递归过程和复杂度

4. 掌握优化：学习记忆化、迭代转换等优化技术

5. 多实践：解决各种递归问题，积累经验

【常见错误】

1. 无限递归：忘记边界条件或边界条件错误

2. 栈溢出：递归深度过大，改为迭代

3. 重复计算：未使用记忆化，指数级复杂度

4. 逻辑错误：递推关系不正确

5. 状态污染：错误使用全局变量

【性能优化】

1. 记忆化：缓存计算结果

2. 尾递归优化：某些编译器可优化

3. 迭代转换：使用栈模拟递归

4. 动态规划：自底向上计算

5. 剪枝：提前终止不可能的分支

【调试技巧】

1. 打印递归深度：cout << "递归深度: " << depth << endl;

2. 小数据测试：验证边界情况和简单情况

3. 画递归树：可视化递归过程

4. 使用调试器：跟踪调用栈

5. 对比迭代版本：验证递归正确性

【扩展应用】

1. 回溯算法：N皇后、数独求解

2. 分治算法：最近点对、矩阵乘法

3. 树形DP：树上动态规划

4. 图遍历：深度优先搜索

5. 函数式编程：递归是函数式编程的核心

1.2 网格DFS与BFS模板（课程04）

📦 核心代码模板

xxxxxxxxxx
// ==================== 网格DFS与BFS模板 ====================

/************************************************************************
 * 1. BFS求最短路径通用模板 (P1443 马的遍历)
 * 问题：在网格中找到从起点到终点的最短路径长度（无权图）
 * 解法：广度优先搜索，队列实现，最先到达终点的路径最短
 * 时间复杂度：O(n×m)，空间复杂度：O(n×m)
 ***********************************************************************/
// 8个方向（马走日）
vector<i64> dx_horse = {-2, -2, -1, -1, 1, 1, 2, 2};
vector<i64> dy_horse = {-1, 1, -2, 2, -2, 2, -1, 1};

// 4个方向（上下左右）
vector<i64> dx_4 = {0, 0, 1, -1};
vector<i64> dy_4 = {1, -1, 0, 0};

// 8个方向（包括对角线）
vector<i64> dx_8 = {0, 0, 1, -1, 1, 1, -1, -1};
vector<i64> dy_8 = {1, -1, 0, 0, 1, -1, 1, -1};

i64 bfs_min_steps(i64 n, i64 m, i64 start_x, i64 start_y, 
                  i64 target_x, i64 target_y, 
                  const vector<i64>& dx, const vector<i64>& dy) {
    // 边界检查
    if (start_x < 0 || start_x >= n || start_y < 0 || start_y >= m ||
        target_x < 0 || target_x >= n || target_y < 0 || target_y >= m) {
        return -1;
    }
    
    // 距离数组，-1表示未访问
    vector<vector<i64>> dist(n, vector<i64>(m, -1));
    dist[start_x][start_y] = 0;
    
    // 使用队列进行BFS
    queue<pair<i64, i64>> q;
    q.push({start_x, start_y});
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 如果到达目标点，返回距离
        if (x == target_x && y == target_y) {
            return dist[x][y];
        }
        
        // 遍历所有可能的方向
        for (i64 i = 0; i < dx.size(); i++) {
            i64 nx = x + dx[i];
            i64 ny = y + dy[i];
            
            // 检查新位置是否合法且未访问
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 不可达
}

// 马的遍历专用函数
i64 bfs_horse(i64 n, i64 m, i64 start_x, i64 start_y, i64 target_x, i64 target_y) {
    return bfs_min_steps(n, m, start_x, start_y, target_x, target_y, dx_horse, dy_horse);
}

// 获取完整距离矩阵（不只是到目标点的距离）
vector<vector<i64>> bfs_all_distances(i64 n, i64 m, i64 start_x, i64 start_y,
                                      const vector<i64>& dx, const vector<i64>& dy) {
    vector<vector<i64>> dist(n, vector<i64>(m, -1));
    dist[start_x][start_y] = 0;
    
    queue<pair<i64, i64>> q;
    q.push({start_x, start_y});
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for (i64 i = 0; i < dx.size(); i++) {
            i64 nx = x + dx[i];
            i64 ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return dist;
}


/************************************************************************
 * 2. BFS连通块计数 (P1451 细胞)
 * 问题：统计网格中连通区域的数量
 * 解法：对每个未访问的1进行BFS，标记整个连通区域
 * 时间复杂度：O(n×m)，空间复杂度：O(n×m)
 ***********************************************************************/
i64 bfs_connected_components(vector<vector<i64>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    
    i64 m = grid.size();
    i64 n = grid[0].size();
    
    // 访问标记数组
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    i64 components = 0;
    
    // 4个方向（上下左右）
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
    for (i64 i = 0; i < m; i++) {
        for (i64 j = 0; j < n; j++) {
            // 找到未访问的单元格且值为1（表示细胞）
            if (grid[i][j] == 1 && !visited[i][j]) {
                components++;
                
                // BFS遍历整个连通区域
                queue<pair<i64, i64>> q;
                q.push({i, j});
                visited[i][j] = true;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    
                    // 遍历4个方向
                    for (i64 d = 0; d < 4; d++) {
                        i64 nx = x + dx[d];
                        i64 ny = y + dy[d];
                        
                        // 检查边界和访问条件
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                            grid[nx][ny] == 1 && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    
    return components;
}

// 8方向连通（包括对角线）
i64 bfs_connected_components_8dir(vector<vector<i64>>& grid) {
    if (grid.empty() || grid[0].empty()) return 0;
    
    i64 m = grid.size();
    i64 n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    i64 components = 0;
    
    // 8个方向（包括对角线）
    vector<i64> dx = {0, 0, 1, -1, 1, 1, -1, -1};
    vector<i64> dy = {1, -1, 0, 0, 1, -1, 1, -1};
    
    for (i64 i = 0; i < m; i++) {
        for (i64 j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                components++;
                
                queue<pair<i64, i64>> q;
                q.push({i, j});
                visited[i][j] = true;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    
                    for (i64 d = 0; d < 8; d++) {
                        i64 nx = x + dx[d];
                        i64 ny = y + dy[d];
                        
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                            grid[nx][ny] == 1 && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    
    return components;
}

// 获取每个连通区域的大小
vector<i64> get_component_sizes(vector<vector<i64>>& grid) {
    if (grid.empty() || grid[0].empty()) return {};
    
    i64 m = grid.size();
    i64 n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<i64> sizes;
    
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
    for (i64 i = 0; i < m; i++) {
        for (i64 j = 0; j < n; j++) {
            if (grid[i][j] == 1 && !visited[i][j]) {
                i64 size = 0;
                
                queue<pair<i64, i64>> q;
                q.push({i, j});
                visited[i][j] = true;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    size++;
                    
                    for (i64 d = 0; d < 4; d++) {
                        i64 nx = x + dx[d];
                        i64 ny = y + dy[d];
                        
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                            grid[nx][ny] == 1 && !visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
                
                sizes.push_back(size);
            }
        }
    }
    
    return sizes;
}


/************************************************************************
 * 3. 滑雪问题 - DFS记忆化搜索 (LS1117)
 * 问题：找到最长的严格递减路径（只能从高到低）
 * 解法：DFS+记忆化，对每个点计算从该点出发的最长路径
 * 时间复杂度：O(n×m)，空间复杂度：O(n×m)
 ***********************************************************************/
class SkiSolver {
private:
    vector<vector<i64>> grid;
    vector<vector<i64>> memo;
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    i64 m, n;
    
    // DFS计算从(x,y)出发的最长滑雪路径
    i64 dfs(i64 x, i64 y) {
        // 如果已经计算过，直接返回
        if (memo[x][y] != -1) {
            return memo[x][y];
        }
        
        // 从当前点出发至少长度为1
        i64 max_len = 1;
        
        // 尝试4个方向
        for (i64 d = 0; d < 4; d++) {
            i64 nx = x + dx[d];
            i64 ny = y + dy[d];
            
            // 检查新位置是否合法且高度更低
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                grid[nx][ny] < grid[x][y]) {
                // 递归计算从新位置出发的路径长度
                i64 len_from_next = dfs(nx, ny) + 1;
                max_len = max(max_len, len_from_next);
            }
        }
        
        // 记忆化
        memo[x][y] = max_len;
        return max_len;
    }
    
public:
    SkiSolver(vector<vector<i64>>& heights) : grid(heights) {
        m = grid.size();
        n = grid[0].size();
        memo.assign(m, vector<i64>(n, -1));
    }
    
    i64 longest_path() {
        i64 max_path = 0;
        
        // 对每个点计算最长路径
        for (i64 i = 0; i < m; i++) {
            for (i64 j = 0; j < n; j++) {
                i64 path_len = dfs(i, j);
                max_path = max(max_path, path_len);
            }
        }
        
        return max_path;
    }
    
    // 获取最长路径的起点和具体路径
    pair<pair<i64, i64>, vector<pair<i64, i64>>> get_longest_path_details() {
        i64 max_path = 0;
        pair<i64, i64> start_point = {0, 0};
        
        // 先找到最长路径的起点
        for (i64 i = 0; i < m; i++) {
            for (i64 j = 0; j < n; j++) {
                i64 path_len = dfs(i, j);
                if (path_len > max_path) {
                    max_path = path_len;
                    start_point = {i, j};
                }
            }
        }
        
        // 重构最长路径
        vector<pair<i64, i64>> path;
        i64 x = start_point.first, y = start_point.second;
        path.push_back({x, y});
        
        while (true) {
            bool found_next = false;
            
            for (i64 d = 0; d < 4; d++) {
                i64 nx = x + dx[d];
                i64 ny = y + dy[d];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    grid[nx][ny] < grid[x][y] &&
                    memo[nx][ny] == memo[x][y] - 1) {
                    x = nx;
                    y = ny;
                    path.push_back({x, y});
                    found_next = true;
                    break;
                }
            }
            
            if (!found_next) break;
        }
        
        return {start_point, path};
    }
};

// 简化接口函数
i64 longest_ski_path(vector<vector<i64>>& grid) {
    SkiSolver solver(grid);
    return solver.longest_path();
}


/************************************************************************
 * 4. 01背包递归+记忆化版本 (LS1082)
 * 问题：经典01背包问题的递归解法
 * 解法：递归考虑选或不选当前物品，使用记忆化避免重复计算
 * 时间复杂度：O(n×capacity)，空间复杂度：O(n×capacity)
 ***********************************************************************/
i64 knapsack_01_recursive(i64 i, i64 capacity,
                         vector<i64>& weights, vector<i64>& values,
                         vector<vector<i64>>& memo) {
    // 边界条件：没有物品或容量为0
    if (i == 0 || capacity == 0) {
        return 0;
    }
    
    // 如果已经计算过，直接返回
    if (memo[i][capacity] != -1) {
        return memo[i][capacity];
    }
    
    // 不选第i个物品（索引i-1）
    i64 result = knapsack_01_recursive(i - 1, capacity, weights, values, memo);
    
    // 如果可以选第i个物品，考虑选的情况
    if (weights[i - 1] <= capacity) {
        i64 take = values[i - 1] + 
                   knapsack_01_recursive(i - 1, capacity - weights[i - 1], 
                                        weights, values, memo);
        result = max(result, take);
    }
    
    // 记忆化
    memo[i][capacity] = result;
    return result;
}

// 包装函数
i64 knapsack_01_memoization(i64 n, i64 capacity,
                           vector<i64>& weights, vector<i64>& values) {
    // 记忆化数组，memo[i][j]表示前i个物品容量为j时的最大价值
    vector<vector<i64>> memo(n + 1, vector<i64>(capacity + 1, -1));
    return knapsack_01_recursive(n, capacity, weights, values, memo);
}


/************************************************************************
 * 5. 完全背包递归+记忆化版本 (LS1083)
 * 问题：完全背包问题的递归解法
 * 解法：与01背包的区别在于选物品时可以重复选择
 * 时间复杂度：O(n×capacity)，空间复杂度：O(n×capacity)
 ***********************************************************************/
i64 knapsack_complete_recursive(i64 i, i64 capacity,
                               vector<i64>& weights, vector<i64>& values,
                               vector<vector<i64>>& memo) {
    // 边界条件
    if (i == 0 || capacity == 0) {
        return 0;
    }
    
    // 记忆化检查
    if (memo[i][capacity] != -1) {
        return memo[i][capacity];
    }
    
    // 不选第i个物品
    i64 result = knapsack_complete_recursive(i - 1, capacity, 
                                            weights, values, memo);
    
    // 如果可以选第i个物品，考虑选的情况
    // 注意：完全背包中，选了之后还可以继续选同一个物品
    if (weights[i - 1] <= capacity) {
        i64 take = values[i - 1] + 
                   knapsack_complete_recursive(i, capacity - weights[i - 1],
                                              weights, values, memo);
        result = max(result, take);
    }
    
    // 记忆化
    memo[i][capacity] = result;
    return result;
}

// 包装函数
i64 knapsack_complete_memoization(i64 n, i64 capacity,
                                 vector<i64>& weights, vector<i64>& values) {
    vector<vector<i64>> memo(n + 1, vector<i64>(capacity + 1, -1));
    return knapsack_complete_recursive(n, capacity, weights, values, memo);
}


/************************************************************************
 * 6. 迷宫连通性检查 (B3625 能否通过迷宫)
 * 问题：判断从起点是否能到达终点
 * 解法：BFS或DFS遍历，检查是否能到达终点
 * 时间复杂度：O(n×m)，空间复杂度：O(n×m)
 ***********************************************************************/
bool can_reach_destination(vector<vector<i64>>& maze,
                          i64 start_x, i64 start_y,
                          i64 target_x, i64 target_y) {
    if (maze.empty() || maze[0].empty()) return false;
    
    i64 m = maze.size();
    i64 n = maze[0].size();
    
    // 边界检查
    if (start_x < 0 || start_x >= m || start_y < 0 || start_y >= n ||
        target_x < 0 || target_x >= m || target_y < 0 || target_y >= n) {
        return false;
    }
    
    // 起点或终点不可达
    if (maze[start_x][start_y] == 0 || maze[target_x][target_y] == 0) {
        return false;
    }
    
    // BFS遍历
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<pair<i64, i64>> q;
    
    q.push({start_x, start_y});
    visited[start_x][start_y] = true;
    
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 到达终点
        if (x == target_x && y == target_y) {
            return true;
        }
        
        // 遍历4个方向
        for (i64 d = 0; d < 4; d++) {
            i64 nx = x + dx[d];
            i64 ny = y + dy[d];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                maze[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    
    return false;
}


/************************************************************************
 * 7. 传送迷宫问题 (P1825 传送迷宫)
 * 问题：迷宫中有传送门，可以瞬间传送到另一位置
 * 解法：BFS处理普通移动和传送
 * 时间复杂度：O(n×m)，空间复杂度：O(n×m)
 ***********************************************************************/
struct Portal {
    i64 x1, y1, x2, y2;
};

i64 bfs_with_portals(vector<vector<i64>>& maze,
                    i64 start_x, i64 start_y,
                    i64 target_x, i64 target_y,
                    vector<Portal>& portals) {
    i64 m = maze.size();
    i64 n = maze[0].size();
    
    // 距离数组
    vector<vector<i64>> dist(m, vector<i64>(n, -1));
    dist[start_x][start_y] = 0;
    
    // 传送门映射：从位置到传送到的位置列表
    vector<vector<vector<pair<i64, i64>>>> portal_map(m, 
        vector<vector<pair<i64, i64>>>(n));
    
    for (const auto& portal : portals) {
        if (maze[portal.x1][portal.y1] == 1 && maze[portal.x2][portal.y2] == 1) {
            portal_map[portal.x1][portal.y1].push_back({portal.x2, portal.y2});
            portal_map[portal.x2][portal.y2].push_back({portal.x1, portal.y1});
        }
    }
    
    queue<pair<i64, i64>> q;
    q.push({start_x, start_y});
    
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        // 到达终点
        if (x == target_x && y == target_y) {
            return dist[x][y];
        }
        
        // 情况1：普通移动
        for (i64 d = 0; d < 4; d++) {
            i64 nx = x + dx[d];
            i64 ny = y + dy[d];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                maze[nx][ny] == 1 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
        
        // 情况2：传送门移动
        for (const auto& [nx, ny] : portal_map[x][y]) {
            if (dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;  // 传送算一步
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 不可达
}


/************************************************************************
 * 8. 推箱子问题简化版 (LS1217 推箱子1)
 * 问题：人在迷宫中推箱子到目标位置
 * 解法：BFS搜索状态空间（人位置+箱子位置）
 * 时间复杂度：O(m²×n²)，空间复杂度：O(m²×n²)
 ***********************************************************************/
struct PushBoxState {
    i64 person_x, person_y;  // 人位置
    i64 box_x, box_y;        // 箱子位置
    i64 steps;               // 已走步数
    
    // 用于unordered_set的哈希函数
    size_t hash() const {
        return ((person_x * 1000 + person_y) * 1000000 +
                (box_x * 1000 + box_y));
    }
    
    bool operator==(const PushBoxState& other) const {
        return person_x == other.person_x && person_y == other.person_y &&
               box_x == other.box_x && box_y == other.box_y;
    }
};

// 自定义哈希函数
struct PushBoxStateHash {
    size_t operator()(const PushBoxState& state) const {
        return state.hash();
    }
};

i64 push_box_min_steps(vector<vector<i64>>& maze,
                      i64 start_person_x, i64 start_person_y,
                      i64 start_box_x, i64 start_box_y,
                      i64 target_x, i64 target_y) {
    i64 m = maze.size();
    i64 n = maze[0].size();
    
    // 初始状态
    PushBoxState start_state = {start_person_x, start_person_y,
                                start_box_x, start_box_y, 0};
    
    // 状态队列
    queue<PushBoxState> q;
    q.push(start_state);
    
    // 状态访问记录
    unordered_set<PushBoxState, PushBoxStateHash> visited;
    visited.insert(start_state);
    
    // 4个方向
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
    while (!q.empty()) {
        auto state = q.front();
        q.pop();
        
        // 箱子到达目标位置
        if (state.box_x == target_x && state.box_y == target_y) {
            return state.steps;
        }
        
        // 人尝试向4个方向移动
        for (i64 d = 0; d < 4; d++) {
            i64 nx = state.person_x + dx[d];
            i64 ny = state.person_y + dy[d];
            
            // 检查新位置是否合法
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 0) {
                continue;
            }
            
            // 新位置
            i64 new_box_x = state.box_x;
            i64 new_box_y = state.box_y;
            
            // 如果人移动到箱子的位置，需要推动箱子
            if (nx == state.box_x && ny == state.box_y) {
                i64 box_nx = state.box_x + dx[d];
                i64 box_ny = state.box_y + dy[d];
                
                // 检查箱子新位置是否合法
                if (box_nx < 0 || box_nx >= m || box_ny < 0 || box_ny >= n ||
                    maze[box_nx][box_ny] == 0) {
                    continue;  // 箱子不能移动
                }
                
                new_box_x = box_nx;
                new_box_y = box_ny;
            }
            
            // 创建新状态
            PushBoxState new_state = {nx, ny, new_box_x, new_box_y, state.steps + 1};
            
            // 如果状态未访问过
            if (visited.find(new_state) == visited.end()) {
                visited.insert(new_state);
                q.push(new_state);
            }
        }
    }
    
    return -1;  // 不可达
}


/************************************************************************
 * 9. 网格DFS通用模板
 * 问题：深度优先搜索解决网格问题
 * 解法：递归探索所有路径，可以结合记忆化和剪枝
 * 时间复杂度：取决于具体问题，空间复杂度：O(n×m)
 ***********************************************************************/
class GridDFS {
private:
    vector<vector<i64>> grid;
    vector<vector<bool>> visited;
    i64 m, n;
    vector<i64> dx = {0, 0, 1, -1};
    vector<i64> dy = {1, -1, 0, 0};
    
public:
    GridDFS(vector<vector<i64>>& g) : grid(g) {
        m = grid.size();
        n = grid[0].size();
        visited.assign(m, vector<bool>(n, false));
    }
    
    // 简单的DFS遍历（连通区域）
    void dfs_simple(i64 x, i64 y) {
        visited[x][y] = true;
        
        for (i64 d = 0; d < 4; d++) {
            i64 nx = x + dx[d];
            i64 ny = y + dy[d];
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                !visited[nx][ny] && grid[nx][ny] == grid[x][y]) {
                dfs_simple(nx, ny);
            }
        }
    }
    
    // 统计连通区域数量
    i64 count_components() {
        i64 count = 0;
        
        for (i64 i = 0; i < m; i++) {
            for (i64 j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    count++;
                    dfs_simple(i, j);
                }
            }
        }
        
        return count;
    }
    
    // 寻找所有路径（回溯法）
    void find_all_paths(i64 start_x, i64 start_y, i64 target_x, i64 target_y,
                       vector<pair<i64, i64>>& current_path,
                       vector<vector<pair<i64, i64>>>& all_paths) {
        // 标记访问
        visited[start_x][start_y] = true;
        current_path.push_back({start_x, start_y});
        
        // 到达终点
        if (start_x == target_x && start_y == target_y) {
            all_paths.push_back(current_path);
        } else {
            // 尝试4个方向
            for (i64 d = 0; d < 4; d++) {
                i64 nx = start_x + dx[d];
                i64 ny = start_y + dy[d];
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    !visited[nx][ny] && grid[nx][ny] == 1) {
                    find_all_paths(nx, ny, target_x, target_y, current_path, all_paths);
                }
            }
        }
        
        // 回溯
        visited[start_x][start_y] = false;
        current_path.pop_back();
    }
    
    // 获取所有从起点到终点的路径
    vector<vector<pair<i64, i64>>> get_all_paths(i64 start_x, i64 start_y,
                                                i64 target_x, i64 target_y) {
        // 重置访问数组
        visited.assign(m, vector<bool>(n, false));
        
        vector<vector<pair<i64, i64>>> all_paths;
        vector<pair<i64, i64>> current_path;
        
        find_all_paths(start_x, start_y, target_x, target_y, current_path, all_paths);
        
        return all_paths;
    }
};


/************************************************************************
 * 10. 网格搜索工具类
 * 提供常用的BFS/DFS辅助函数
 ***********************************************************************/
class GridSearchTools {
public:
    // 方向数组生成
    static vector<pair<i64, i64>> get_directions_4() {
        return {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    }
    
    static vector<pair<i64, i64>> get_directions_8() {
        return {{0, 1}, {0, -1}, {1, 0}, {-1, 0},
                {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    }
    
    static vector<pair<i64, i64>> get_horse_moves() {
        return {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},
                {1, -2}, {1, 2}, {2, -1}, {2, 1}};
    }
    
    // 检查位置是否在网格内
    static bool is_valid_position(i64 x, i64 y, i64 m, i64 n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    
    // 打印路径（调试用）
    static void print_path(const vector<pair<i64, i64>>& path) {
        cout << "路径 (" << path.size() << "步): ";
        for (size_t i = 0; i < path.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << "(" << path[i].first << "," << path[i].second << ")";
        }
        cout << "\n";
    }
    
    // 打印网格状态
    static void print_grid(const vector<vector<i64>>& grid) {
        cout << "网格 (" << grid.size() << "×" 
             << (grid.empty() ? 0 : grid[0].size()) << "):\n";
        for (const auto& row : grid) {
            cout << "  ";
            for (i64 val : row) {
                cout << (val == 0 ? "█" : "·") << " ";
            }
            cout << "\n";
        }
    }
    
    // 生成随机迷宫
    static vector<vector<i64>> generate_random_maze(i64 m, i64 n, double obstacle_ratio = 0.3) {
        vector<vector<i64>> maze(m, vector<i64>(n, 1));
        srand(time(0));
        
        for (i64 i = 0; i < m; i++) {
            for (i64 j = 0; j < n; j++) {
                if ((double)rand() / RAND_MAX < obstacle_ratio) {
                    maze[i][j] = 0;  // 障碍物
                }
            }
        }
        
        // 确保起点和终点是通的
        maze[0][0] = 1;
        maze[m-1][n-1] = 1;
        
        return maze;
    }
};