题解：石头跳跃游戏的最优解

题意分析

题目描述了一个在无限网格上的石头跳跃游戏，规则类似于跳棋：

1. 初始有$m \times n$的矩形石头阵列
2. 石头可以水平或垂直跳过相邻石头，被跳过的石头会被移除
3. 目标是通过一系列操作使剩余石头数量最少

解题思路

通过数学分析可以发现：

1. 当$m$或$n$是$3$的倍数时，最少可以剩下2颗石头
2. 当$m$或$n$为$1$或$2$时，最少可以剩下$\lceil \frac{max(m,n)}{2} \rceil$颗石头
3. 其他情况下，最少可以剩下$1$颗石头

实现步骤

1. 输入处理：读取$m$和$n$的值
2. 大小排序：确保$m \geq n$以简化判断
3. 条件判断：
   • 检查是否为1或2的特殊情况
   • 检查是否为3的倍数
   • 默认情况处理
4. 结果输出：根据条件输出最少剩余石头数

代码注释

#include <iostream>
using namespace std;

int main() {
    int m, n, t;  // 定义变量：m行数，n列数，t临时变量
    
    // 循环读取输入（虽然题目可能只给一组输入，但这样写更通用）
    while (cin >> m >> n) {
        // 确保m >= n，简化后续判断
        if (n > m) {
            t = n;
            n = m;
            m = t;
        }
        
        // 特殊情况处理：当n=1或2时
        if (n == 1 || n == 2)
            // 最少剩余石头数为(m+1)/2的整数部分
            cout << (m + 1) / 2 << endl;
        
        // 当m或n是3的倍数时
        else if (n % 3 == 0 || m % 3 == 0)
            // 最少可以剩下2颗石头
            cout << "2" << endl;
        
        // 其他情况
        else
            // 最少可以剩下1颗石头
            cout << "1" << endl;
    }
    
    return 0;  // 程序正常结束
}

复杂度分析

1. 时间复杂度：$O(1)$，只有简单的条件判断
2. 空间复杂度：$O(1)$，只使用了固定数量的变量