题解：UVA141 The Spot Game

· · 题解

浅发一波双哈希题解

### 题目分析 在一个 $N \times N$ 的棋盘上，两名玩家轮流进行操作，每步操作要么在空格子上放置一个棋子（`+`），要么移除一个已有棋子（`-`）。如果当前棋盘状态（包括其旋转 $90^{\circ}$、$180^{\circ}$ 和 $270^{\circ}$ 后的状态）在之前出现过，则当前操作的玩家失败，对手获胜。如果所有 $2N$ 步操作完成后未出现重复状态，则游戏平局。 ### 解题思路 使用二维数组表示棋盘状态，$0$ 表示空格，$1$ 表示棋子。采用双哈希将棋盘状态映射为两个无符号长整数组成的对。 对于每个状态，计算其 $0^{\circ}$、$90^{\circ}$、$180^{\circ}$ 和 $270^{\circ}$ 旋转后的哈希值，并将这 $4$ 个哈希值都存入集合中。后续只需检查其任一旋转的哈希值是否在集合中即可判重。 每一步操作后，计算当前状态的 $4$ 个旋转哈希值，检查集合中是否存在相同哈希值。若存在，则当前操作玩家失败；否则将 $4$ 个哈希值加入集合并继续游戏。 ## $Code 
#include <iostream>
#include <set>       // 集合容器库，用于存储哈希值
#include <utility>   // 工具库，包含pair等
using namespace std;

typedef unsigned long long ull;

// 定义两个不同的哈希基数，用于双哈希减少冲突概率
const ull base1 = 131;
const ull base2 = 13131;

const int MAX_N = 50;

/*
 * 计算棋盘状态的哈希值（使用双哈希技术）
 * @param board 棋盘状态数组
 * @param rot 旋转角度（0:0°, 90:90°, 180:180°, 270:270°）
 * @param n 棋盘实际尺寸
 * @return 包含两个哈希值的pair
 */
pair<ull, ull> compute_hash(int board[MAX_N][MAX_N], int rot, int n) {
    ull hash1 = 0;
    ull hash2 = 0;

    // 根据旋转角度计算哈希值
    if (rot == 0) { // 0°旋转（原始状态）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = board[i][j]; // 获取棋盘当前位置的值
                hash1 = hash1 * base1 + val; // 更新第一个哈希值
                hash2 = hash2 * base2 + val; // 更新第二个哈希值
            }
        }
    } 
    else if (rot == 90) { // 90°顺时针旋转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算旋转后的坐标
                int x = n - 1 - j;
                int y = i;
                int val = board[x][y];
                hash1 = hash1 * base1 + val;
                hash2 = hash2 * base2 + val;
            }
        }
    } 
    else if (rot == 180) { // 180°旋转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算旋转后的坐标
                int x = n - 1 - i;
                int y = n - 1 - j;
                int val = board[x][y];
                hash1 = hash1 * base1 + val;
                hash2 = hash2 * base2 + val;
            }
        }
    } 
    else if (rot == 270) { // 270°顺时针旋转（或90°逆时针）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 计算旋转后的坐标
                int x = j;
                int y = n - 1 - i;
                int val = board[x][y];
                hash1 = hash1 * base1 + val;
                hash2 = hash2 * base2 + val;
            }
        }
    }
    return make_pair(hash1, hash2); // 返回双哈希值
}

int main() {
    int n;
    while (cin >> n && n != 0) { // 读取输入直到遇到0
        int moves[MAX_N*2][3]; 
        for (int i = 0; i < 2 * n; i++) {
            int x, y;
            char op;
            cin >> x >> y >> op;
            // 转换为0-based索引并存储
            moves[i][0] = x - 1;    // x坐标（转换为0-based）
            moves[i][1] = y - 1;    // y坐标（转换为0-based）
            moves[i][2] = (op == '+') ? 1 : 0; // 操作类型：1表示放置，0表示移除
        }

        int board[MAX_N][MAX_N] = {0}; // 初始化棋盘，全部置0
        set<pair<ull, ull>> seen;      // 存储已见过的哈希值集合
        bool found = false;            // 标记是否已找到获胜者

        // 处理每一步操作
        for (int step = 0; step < 2 * n; step++) {
            // 获取当前操作
            int x = moves[step][0];
            int y = moves[step][1];
            int op = moves[step][2];

            // 执行操作：放置或移除棋子
            board[x][y] = op;

            // 计算当前状态及其旋转状态的哈希值
            pair<ull, ull> hashes[4];
            hashes[0] = compute_hash(board, 0, n);   // 原始状态
            hashes[1] = compute_hash(board, 90, n);  // 90°旋转
            hashes[2] = compute_hash(board, 180, n); // 180°旋转
            hashes[3] = compute_hash(board, 270, n); // 270°旋转

            // 检查是否有重复状态
            bool duplicate = false;
            for (int i = 0; i < 4; i++) {
                if (seen.find(hashes[i]) != seen.end()) {
                    duplicate = true;
                    break;
                }
            }

            // 如果发现重复状态
            if (duplicate) {
                // 确定当前玩家（奇数步为玩家1，偶数步为玩家2）
                int player = (step % 2 == 0) ? 1 : 2;
                // 获胜者为对方玩家
                int winner = (player == 1) ? 2 : 1;
                // 输出结果
                cout << "Player " << winner << " wins on move " << step + 1 << '\n';
                found = true;
                break; // 游戏结束，跳出循环
            } 
            else {
                // 如果没有重复，将四个旋转状态的哈希值都存入集合
                for (int i = 0; i < 4; i++) {
                    seen.insert(hashes[i]);
                }
            }
        }

        // 如果所有操作处理完都没有重复状态
        if (!found) {
            cout << "Draw\n"; // 输出平局
        }
    }
    return 0;
}

对于每个游戏，执行 2N 步操作，每步操作需要计算 4 个旋转状态的哈希值，每个哈希值计算需 O(N^2) 时间。总时间复杂度为 O(N^3)，在 N \leq 50 时能过。