题解：棋盘游戏移动枚举（Mid-Central USA 1996）

一、题目分析

本题要求根据棋盘布局枚举指定玩家（X或O）的所有合法移动。关键规则：

1. 棋子可沿水平、垂直或对角线方向直线移动
2. 移动格数等于所在行、列或对角线的总棋子数
3. 可跳过己方棋子，但不能跳过对方棋子
4. 可吃掉对方棋子（落在对方棋子位置）
5. 不能落在己方棋子位置

二、解题思路

1. 方向与移动距离：
   8个移动方向（上下左右、四个对角线），每个方向的移动距离为对应行、列或对角线的棋子总数。

2. 合法性检查：

   • 移动路径上不能有对方棋子（可跳过己方）
   • 目标位置不能是己方棋子
   • 移动距离必须严格等于对应方向的棋子数

3. 实现步骤：

   • 读取棋盘并统计每行每列的棋子数
   • 对每个己方棋子，检查8个方向的合法移动
   • 收集所有合法移动并按字典序排序输出

三、代码解析

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

string p;             // 玩家标识（X或O）
char da[10][10];      // 棋盘（8x8）
int hang[10], lie[10]; // 每行、每列的棋子数
vector<string> jg;    // 存储合法移动

// 查找并记录合法移动
// x,y: 起始坐标，dx,dy: 移动方向，step: 移动格数
void find(int x, int y, int dx, int dy, int step) {
    // 检查移动路径是否合法（不能有对方棋子）
    for (int i = x + dx, j = y + dy, js = 1; js != step; i += dx, j += dy, js++) {
        if (i >= 0 && i < 8 && j >= 0 && j < 8) {
            if (da[i][j] != p[0] && da[i][j] != '.') {
                return; // 路径上有对方棋子，不合法
            }
        } else {
            return; // 超出棋盘范围
        }
    }
    // 检查目标位置是否合法
    int nx = x + step * dx, ny = y + step * dy;
    if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && da[nx][ny] != p[0]) {
        // 构造移动字符串（如A1-A2）
        string fh = "";
        fh += (char)(x + 'A');
        fh += (char)(y + '1');
        fh += '-';
        fh += (char)(nx + 'A');
        fh += (char)(ny + '1');
        jg.push_back(fh);
    }
}

int main() {
    while (1) {
        memset(hang, 0, sizeof(hang));
        memset(lie, 0, sizeof(lie));
        jg.clear();
        
        // 读取棋盘
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                cin >> da[i][j];
                if (cin.eof()) return 0; // 输入结束
                if (da[i][j] != '.') {
                    hang[i]++; // 统计行棋子数
                    lie[j]++; // 统计列棋子数
                }
            }
        }
        
        cin >> p; // 读取玩家标识（X或O）
        
        // 遍历每个己方棋子
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (da[i][j] == p[0]) { // 是己方棋子
                    // 处理水平方向（左右）
                    find(i, j, 1, 0, lie[j]);  // 右移
                    find(i, j, -1, 0, lie[j]); // 左移
                    // 处理垂直方向（上下）
                    find(i, j, 0, 1, hang[i]);  // 下移
                    find(i, j, 0, -1, hang[i]); // 上移
                    
                    // 处理主对角线（右下-左上）
                    int js = 1;
                    for (int ti = i + 1, tj = j + 1; ti < 8 && tj < 8; ti++, tj++)
                        if (da[ti][tj] != '.') js++;
                    for (int ti = i - 1, tj = j - 1; ti >= 0 && tj >= 0; ti--, tj--)
                        if (da[ti][tj] != '.') js++;
                    find(i, j, 1, 1, js);   // 右下
                    find(i, j, -1, -1, js); // 左上
                    
                    // 处理副对角线（左下-右上）
                    js = 1;
                    for (int ti = i + 1, tj = j - 1; ti < 8 && tj >= 0; ti++, tj--)
                        if (da[ti][tj] != '.') js++;
                    for (int ti = i - 1, tj = j + 1; ti >= 0 && tj < 8; ti--, tj++)
                        if (da[ti][tj] != '.') js++;
                    find(i, j, 1, -1, js);  // 左下
                    find(i, j, -1, 1, js);  // 右上
                }
            }
        }
        
        // 输出结果
        if (jg.size() == 0) {
            cout << "No moves are possible" << endl << endl;
        } else {
            sort(jg.begin(), jg.end()); // 字典序排序
            for (int i = 0; i < jg.size(); i++)
                cout << jg[i] << endl;
            cout << endl;
        }
    }
    return 0;
}

四、关键步骤解析

1. 棋盘读取与统计

   • 读取8x8棋盘，统计每行（hang）和每列（lie）的棋子数
   • 棋子包括'X'、'O'，点号（.）表示空位

2. 移动方向处理

   • 水平/垂直方向：移动距离为所在列/行的棋子数
   • 对角线方向：手动统计对角线上的棋子数（包括当前棋子）

3. 合法性检查

   • 路径检查：遍历移动路径上的每个格子，若有对方棋子则非法
   • 边界检查：目标位置不能超出棋盘
   • 落点检查：不能落在己方棋子位置

4. 移动字符串构造

   • 行用A-H表示（i+'A'），列用1-8表示（j+'1'）
   • 格式为"起点-终点"（如A1-A2）

5. 结果处理

   • 收集所有合法移动后按字典序排序
   • 无合法移动时输出"No moves are possible"

五、示例解析

以第一个输入示例为例：

1. 棋盘分析：
   O玩家的棋子分布在A1、B1、C1、D1、E2、G3等位置。
   以A1（i=0,j=0）为例：

   • 所在列j=0的棋子数lie[0]=4（A1、B1、C1、D1）
   • 向右移动4格到E1（i=0,j=4），路径上无对方棋子，合法。

2. 对角线统计：
   主对角线（右下方向）从A1出发，统计对角线上的棋子数：
   A1（O）、B2（.）、C3（O）、D4（O）、E5（O）→ 共4个棋子，移动距离为4。

3. 合法移动生成：
   A1可移动到A2（上移1格，行棋子数1）、C3（主对角线移动4格）、E1（右移4格）等，最终生成29个合法移动。

六、注意事项

1. 坐标转换：

   • 数组索引i对应行（A-H）：i=0→A，i=1→B，…，i=7→H
   • 数组索引j对应列（1-8）：j=0→1，j=1→2，…，j=7→8

2. 移动距离计算：

   • 水平/垂直方向直接使用hang/lie数组统计的棋子数
   • 对角线方向需手动遍历统计

3. 路径检查顺序：
   移动路径从起点的下一个格子开始检查，直到移动距离-1格，确保路径上无对方棋子。

4. 字典序排序：
   C++的$sort$函数对string默认按字典序排序，符合题目要求。

七、复杂度分析

• 时间复杂度：O(8×8×8) = O(512)，每个棋子检查8个方向，每个方向最多检查8格。
• 空间复杂度：O(64)（棋盘）+ O(移动数)，移动数最多为8×8×8=512，总体可忽略。

八、可能的优化

1. 对角线统计优化：
   预计算所有对角线的棋子数，避免重复统计。

2. 方向遍历优化：
   用方向数组$dx[] = {1,-1,0,0,1,-1,1,-1}$和$dy[] = {0,0,1,-1,1,-1,-1,1}$统一处理8个方向。

3. 提前终止：
   路径检查中若发现对方棋子或越界，立即终止该方向检查。