题目描述

在一个标准的 $8\times 8$ 棋盘上，有 $4$ 个相同的棋子。每个移动可以执行以下两种操作之一：

1. 普通移动：将棋子移动到相邻的空格（上、下、左、右）
2. 跳跃移动：跳过相邻的一个棋子落到紧挨着的空格中

给定两个棋盘配置，每个配置由 $8$ 个整数表示（分别描述 $4$ 个棋子的行号和列号），判断是否能在最多 $8$ 步内从第一个配置到达第二个配置。

解题思路

问题分析

这是一个典型的状态空间搜索问题，需要解决以下关键点：

$1$. 状态表示：由于棋子不可区分，我们需要用排序后的位置集合来表示状态
$2$. 状态空间：从 $64$ 个位置中选 $4$ 个，组合数为 $C(64,4)\approx 6.35\times 10^5$
$3$. 步数限制：最多 $8$ 步，限制了搜索深度
$4$. 移动规则：需要正确处理普通移动和跳跃移动

算法选择

考虑到步数限制较小但状态空间较大，我们采用双向 $\text{BFS}$算法：

• 单向 $\text{BFS}$ 复杂度：$O(b^d)$，其中 $b\approx 32$（分支因子），$d=8$ → 约 $32^8$ 个状态
• 双向 $\text{BFS}$ 复杂度：$O(b^{d/2})$ → 约 $32^4$ 个状态，效率提升显著

关键技术细节

1. 状态编码

• 将 $(r,c)$ 坐标编码为 $0-63$ 的整数：$pos=(r-1)\times 8+(c-1)$
• 状态用排序后的 $4$ 个整数向量表示，确保棋子不可区分性

2. 移动生成

对于每个棋子的四个方向：

• 普通移动：检查目标位置是否在棋盘内且为空
• 跳跃移动：检查中间位置有棋子且目标位置在棋盘内且为空

3. 双向 $\text{BFS}$ 实现

• 从起点和终点同时开始搜索
• 使用两个队列和两个哈希集合
• 当两个搜索方向相遇时找到解
• 总步数控制：$step{s}_1+step{s}_2\le 8$

复杂度分析

• 时间复杂度：$O(b^{d/2})=O(32^4)$，在可接受范围内
• 空间复杂度：$O(b^{d/2})$，存储两个方向的已访问状态

优化技巧

1. 哈希优化：使用 unordered_set 和自定义哈希函数
2. $\text{IO}$ 优化：使用 ios::sync_with_stdio(false) 加速输入输出
3. 提前终止：发现相遇立即返回结果

参考代码

// Solitaire
// UVa ID: 1724
// Verdict: Accepted
// Submission Date: 2025-10-15
// UVa Run Time: 0.040s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

// 将行列位置编码为单个整数 (0-63)
int encode(int r, int c) { return (r - 1) * 8 + (c - 1); }

// 检查位置是否在棋盘范围内
bool inBoard(int r, int c) { return r >= 1 && r <= 8 && c >= 1 && c <= 8; }

// 状态类型：排序后的 4 个位置整数
typedef vector<int> State;

// 状态哈希函数
struct StateHash {
    size_t operator()(const State& s) const {
        size_t hash = 0;
        for (int pos : s) {
            hash = hash * 131 + pos;
        }
        return hash;
    }
};

// 生成当前状态的所有下一步可能状态
vector<State> getNextStates(const State& current) {
    vector<State> nextStates;
    // 将当前状态转为集合便于快速查找
    set<int> currentSet(current.begin(), current.end());
    // 四个移动方向：下、上、右、左
    const int dr[] = {1, -1, 0, 0};
    const int dc[] = {0, 0, 1, -1};
    
    // 对每个棋子尝试移动
    for (int i = 0; i < 4; i++) {
        int pos = current[i];
        int r = pos / 8 + 1;
        int c = pos % 8 + 1;
        
        // 尝试四个方向
        for (int dir = 0; dir < 4; dir++) {
            // 尝试普通移动：移动到相邻空位
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            if (inBoard(nr, nc)) {
                int newPos = encode(nr, nc);
                if (currentSet.find(newPos) == currentSet.end()) {
                    State newState = current;
                    newState[i] = newPos;
                    sort(newState.begin(), newState.end());
                    nextStates.push_back(newState);
                }
            }
            
            // 尝试跳跃移动：跳过相邻棋子
            int mr = r + dr[dir];
            int mc = c + dc[dir];
            if (inBoard(mr, mc)) {
                int midPos = encode(mr, mc);
                if (currentSet.find(midPos) != currentSet.end()) {
                    int nr = r + 2 * dr[dir];
                    int nc = c + 2 * dc[dir];
                    if (inBoard(nr, nc)) {
                        int newPos = encode(nr, nc);
                        if (currentSet.find(newPos) == currentSet.end()) {
                            State newState = current;
                            newState[i] = newPos;
                            sort(newState.begin(), newState.end());
                            nextStates.push_back(newState);
                        }
                    }
                }
            }
        }
    }
    return nextStates;
}

// 双向 BFS 检查是否能在 8 步内到达目标状态
bool canReach(const State& startState, const State& targetState) {
    if (startState == targetState) return true;
    
    // 使用两个队列和两个 visited 集合
    queue<State> q1, q2;
    unordered_set<State, StateHash> visited1, visited2;
    
    q1.push(startState);
    q2.push(targetState);
    visited1.insert(startState);
    visited2.insert(targetState);
    
    int steps1 = 0, steps2 = 0;
    
    while (!q1.empty() && !q2.empty()) {
        // 从起点方向扩展一层
        if (steps1 + steps2 < 8) {
            int size1 = q1.size();
            for (int i = 0; i < size1; i++) {
                State current = q1.front();
                q1.pop();
                
                vector<State> nextStates = getNextStates(current);
                for (const State& next : nextStates) {
                    if (visited1.find(next) != visited1.end()) continue;
                    
                    // 检查是否在另一方向已经访问过
                    if (visited2.find(next) != visited2.end()) {
                        return true;
                    }
                    
                    visited1.insert(next);
                    q1.push(next);
                }
            }
            steps1++;
        }
        
        // 从终点方向扩展一层
        if (steps1 + steps2 < 8) {
            int size2 = q2.size();
            for (int i = 0; i < size2; i++) {
                State current = q2.front();
                q2.pop();
                
                vector<State> nextStates = getNextStates(current);
                for (const State& next : nextStates) {
                    if (visited2.find(next) != visited2.end()) continue;
                    
                    // 检查是否在另一方向已经访问过
                    if (visited1.find(next) != visited1.end()) {
                        return true;
                    }
                    
                    visited2.insert(next);
                    q2.push(next);
                }
            }
            steps2++;
        }
        
        // 如果总步数超过 8，停止搜索
        if (steps1 + steps2 >= 8) break;
    }
    
    return false;
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    
    vector<int> start(8), target(8);
    while (cin >> start[0]) {
        for (int i = 1; i < 8; i++) cin >> start[i];
        for (int i = 0; i < 8; i++) cin >> target[i];
        
        State startState, targetState;
        for (int i = 0; i < 4; i++) {
            startState.push_back(encode(start[2 * i], start[2 * i + 1]));
            targetState.push_back(encode(target[2 * i], target[2 * i + 1]));
        }
        
        sort(startState.begin(), startState.end());
        sort(targetState.begin(), targetState.end());
        
        if (canReach(startState, targetState)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

总结

本题通过**双向 $\text{BFS}$**算法高效解决了状态空间搜索问题，关键点在于：

• 合理的状态表示确保棋子不可区分
• 正确的移动规则实现
• 双向搜索大幅减少状态空间
• 严格的步数控制和优化技巧

这种解法在步数限制较小的情况下特别有效，是解决类似棋盘游戏问题的经典方法。