题目分析

这个题目描述了一个名为"Stake Your Claim"的双人棋盘游戏，要求编写一个程序来确定当前玩家的最佳移动策略。

游戏规则：

1. 使用n×n的棋盘，初始有m个0和m个1随机分布
2. 玩家0先手，轮流在空格('.'表示)放置自己的数字
3. 填满棋盘后，计算每个玩家最大连通区域的大小
4. 胜负判定：最大连通区域大的玩家获胜，得分差为两者区域大小之差

解题思路

1. 状态表示：

   • 使用位压缩存储棋盘状态（每个空格用2位表示）
   • 预处理所有空格的位置

2. 连通区域计算：

   • 使用DFS/BFS计算最大连通区域
   • 需要临时标记已访问的位置

3. 博弈树搜索：

   • 使用记忆化搜索(DFS+记忆化)
   • 当前玩家选择最大化自己得分
   • 对手选择最小化当前玩家得分

4. 优化策略：

   • 状态压缩减少内存使用
   • 记忆化搜索避免重复计算
   • 提前终止不必要的搜索路径

优化后的标程代码

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

const int INF = 1e9;
const int MAXN = 8;
char board[MAXN][MAXN];
vector<pair<int, int>> emptyCells;
int n;
int memo[1 << 20]; // 足够大的空间存储状态

// 计算当前棋盘下各玩家的最大连通区域
pair<int, int> calculateRegions() {
    bool visited[MAXN][MAXN] = {false};
    int max0 = 0, max1 = 0;
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!visited[i][j] && board[i][j] != '.') {
                char current = board[i][j];
                int count = 0;
                vector<pair<int, int>> stack = {{i, j}};
                visited[i][j] = true;
                
                while (!stack.empty()) {
                    auto [x, y] = stack.back();
                    stack.pop_back();
                    count++;
                    
                    // 四个方向检查
                    const int dx[] = {0, 0, 1, -1};
                    const int dy[] = {1, -1, 0, 0};
                    
                    for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                            !visited[nx][ny] && board[nx][ny] == current) {
                            visited[nx][ny] = true;
                            stack.emplace_back(nx, ny);
                        }
                    }
                }
                
                if (current == '0') max0 = max(max0, count);
                else max1 = max(max1, count);
            }
        }
    }
    
    return {max0, max1};
}

// 极小极大搜索
int minimax(int state, int player, int remaining) {
    if (memo[state] != -INF) return memo[state];
    
    if (remaining == 0) {
        auto [max0, max1] = calculateRegions();
        memo[state] = max0 - max1;
        return memo[state];
    }
    
    int bestValue = (player == 0) ? -INF : INF;
    
    for (int i = 0; i < emptyCells.size(); ++i) {
        if (!(state & (1 << (2*i))) && !(state & (1 << (2*i+1)))) {
            int newState = state;
            if (player == 0) newState |= (1 << (2*i));   // 玩家0放置0
            else newState |= (1 << (2*i+1));             // 玩家1放置1
            
            int value = minimax(newState, 1 - player, remaining - 1);
            
            if (player == 0) bestValue = max(bestValue, value);
            else bestValue = min(bestValue, value);
        }
    }
    
    memo[state] = bestValue;
    return bestValue;
}

int main() {
    while (cin >> n && n) {
        emptyCells.clear();
        int zeroCount = 0, oneCount = 0;
        
        for (int i = 0; i < n; ++i) {
            cin >> board[i];
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '0') zeroCount++;
                else if (board[i][j] == '1') oneCount++;
                else emptyCells.emplace_back(i, j);
            }
        }
        
        // 初始化记忆化数组
        fill(memo, memo + (1 << 20), -INF);
        
        int currentPlayer = (zeroCount > oneCount) ? 1 : 0;
        int bestScore = minimax(0, currentPlayer, emptyCells.size());
        
        // 寻找最佳移动
        pair<int, int> bestMove;
        int foundScore = -INF;
        
        for (int i = 0; i < emptyCells.size(); ++i) {
            int newState = (currentPlayer == 0) ? (1 << (2*i)) : (1 << (2*i+1));
            int score = minimax(newState, 1 - currentPlayer, emptyCells.size() - 1);
            
            if (currentPlayer == 0) {
                if (score > foundScore || 
                    (score == foundScore && emptyCells[i] < bestMove)) {
                    foundScore = score;
                    bestMove = emptyCells[i];
                }
            } else {
                if (score < foundScore || 
                    (score == foundScore && emptyCells[i] < bestMove)) {
                    foundScore = score;
                    bestMove = emptyCells[i];
                }
            }
        }
        
        // 调整分数显示
        if (currentPlayer == 1) foundScore = -foundScore;
        printf("(%d,%d) %d\n", bestMove.first, bestMove.second, foundScore);
    }
    
    return 0;
}

代码说明

1. 状态表示：

   • 使用20位整数表示状态（最多10个空格，每个空格用2位表示）
   • 偶数位表示玩家0的选择，奇数位表示玩家1的选择

2. 核心函数：

   • calculateRegions()：计算当前棋盘的最大连通区域
   • minimax()：实现极小极大算法，带记忆化

3. 优化措施：

   • 记忆化搜索避免重复计算
   • 按字典序遍历空格位置
   • 提前确定当前玩家（0或1）

4. 输入输出：

   • 处理多组测试数据
   • 输出最佳移动坐标和得分差

这个实现比原代码更清晰易读，同时保持了相同的算法思想，适合作为竞赛的标准解答。