题目描述

给定一个 7×7 的孔洞棋盘。某些孔洞中放有钉子（peg），某些则没有。你可以让一个钉子跳过相邻的钉子，只要跳跃后落地的孔洞是空的。被跳过的钉子会被移除。你的目标是让棋盘上最终只剩一个钉子，并且该钉子必须落在指定的位置。

棋盘用一个 7×7 的字符矩阵表示，各字符含义如下：

• x：该孔洞永远不能放置钉子。
• e：该孔洞初始为空。
• o：该孔洞初始有一个钉子。
• E：该孔洞初始为空，且最后一个钉子必须落在此处。
• O：该孔洞初始有一个钉子，且最后一个钉子必须落在此处。

示例

例如，给定以下棋盘：

x x e e e x x  
x x o e e x x  
e e o e e e e  
e e o O e e e  
e e e e e e e  
x x e e e x x  
x x e e e x x  

可以看到初始有 4 个钉子（o 或 O），且最后一个钉子需要落在棋盘中央（O 的位置）。

获胜的移动序列为：

1. (4, 4) 到 (2, 4)
2. (3, 2) 到 (3, 4)
3. (2, 4) 到 (4, 4)

其中坐标格式为 (行, 列)，行列均从 1 开始计数。

输入格式

• 第一行输入为数据集的数量。
• 每个数据集由 7 行组成，每行包含 7 个字符（x、e、o、E、O），字符之间用空格分隔。
• 保证每个数据集中有且仅有一个 E 或 O，且至少有两个 o 或 O。

输出格式

• 对于每个数据集，输出一行 Dataset X:，其中 X 是数据集编号（从 1 开始）。
• 如果存在有效的移动序列使得棋盘最终只剩一个钉子并落在指定位置，则按顺序输出移动步骤，每步格式为：
  序号. (x1, y1) to (x2, y2)
  （坐标表示 (行, 列)，从 1 开始计数）。
• 如果无解，输出 No solution.。
• 不同数据集之间用空行分隔。

示例输入 1

2
x x e e e x x
x x o e e x x
e e o e e e e
e e o O e e e
e e e e e e e
x x e e e x x
x x e e e x x
x x e E e e e
x e e e e e e
e e e o o e e
e e e x e e e
e e e e e e e
e e e e e e e
e e e e e e e

示例输出 1

Dataset 1:
1. (4, 4) to (2, 4)
2. (3, 2) to (3, 4)
3. (2, 4) to (4, 4)

Dataset 2:
No solution.

提示

• 移动方向搜索顺序：上、左、下、右。

来源

Greater New York 2003

解题思路

这道题目是一个经典的 Peg Solitaire（孔明棋） 问题，要求通过合法的跳跃移动让棋盘最终只剩一颗钉子并落在指定位置（标记为 E 或 O）。解题采用 回溯法（Backtracking）+ 深度优先搜索（DFS） 的策略：首先初始化棋盘状态，记录钉子位置和可移动区域；然后通过 forward 函数尝试所有可能的跳跃移动（按左、上、右、下的顺序检查），若移动合法则更新棋盘状态；若当前路径无法达成目标，则通过 backward 函数回溯并恢复之前的状态，继续搜索其他可能性。关键优化包括搜索顺序的优先级和及时剪枝，避免无效计算。最终若有解，则输出移动序列（格式为 序号. (x1,y1) to (x2,y2)），否则返回无解。该算法高效遍历状态空间，适用于此类棋盘跳跃问题。

C++实现

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string.h>
#include <math.h>
#include <list>
#include <set>
using namespace std;

int move_p[40], move_d[50], move_j[50], move_l[50];
bool pegs[50], allow[50];
int orig;
int num;
int last;
int next_peg, next_dir;

bool forward_helper(int curr, int dir, int & jump, int & land) {
    const int curr_x = curr % 7;
    const int curr_y = curr / 7;
    int jump_x = curr_x;
    int jump_y = curr_y;
    int land_x = curr_x;
    int land_y = curr_y;
    switch (dir)
       {
       case 0:
          jump_x = curr_x - 1;
          land_x = curr_x - 2;
          break;
       case 1:
          jump_y = curr_y - 1;
          land_y = curr_y - 2;
          break;
       case 2:
          jump_x = curr_x + 1;
          land_x = curr_x + 2;
          break;
       case 3:
          jump_y = curr_y + 1;
          land_y = curr_y + 2;
          break;
       }

    if ((land_x < 0) || (land_x >= 7) ||
        (land_y < 0) || (land_y >= 7)) return false;

    jump = jump_x + 7 * jump_y;
    land = land_x + 7 * land_y;
    return true;
}

inline void increment_p() {
    next_dir = 0;
    next_peg++;
}

inline void increment() {
    next_dir++;
    if (next_dir == 4) increment_p(); 
}

bool forward(void) {
    const int index = orig - num;
    if (num == 1) return false;
    while (next_peg < 49) {
        int jump, land;
        if (!pegs[next_peg])
            increment_p();
        else if (forward_helper(next_peg, next_dir, jump, land)
                 && pegs[jump] && !pegs[land] && allow[land]) {
            move_p[index] = next_peg;
            move_d[index] = next_dir;
            move_j[index] = jump;
            move_l[index] = land;

            pegs[next_peg] = false;
            pegs[jump] = false;
            pegs[land] = true;
            --num;
            next_peg = 0;
            next_dir = 0;

            return true;
         } else increment();
    }

    return false;
}

inline bool win() {return (num == 1) && pegs[last];}

void print() {
    for (int i = 0; i < orig - 1; ++i) {
        const int orig = move_p[i];
        const int land = move_l[i];
        const int orig_x = orig % 7 + 1;
        const int orig_y = orig / 7 + 1;
        const int land_x = land % 7 + 1;
        const int land_y = land / 7 + 1;
        cout << (i+1) << ". (" << orig_x << ", " << orig_y << ") to (" << land_x << ", " << land_y <<")" << endl;
    }
}

bool backward() {
    const int index = orig - num - 1;
    if (index < 0) return false;

    next_peg = move_p[index];
    next_dir = move_d[index];
    const int jump = move_j[index];
    const int land = move_l[index];
    ++num;
    pegs[next_peg] = true;
    pegs[jump] = true;
    pegs[land] = false;

    increment();

    return true;
}

void go() {
    while (1) {
        if (forward()) {
            if (win()) {
                print();
                return;
            }
        } else if (backward()) {
        } else break;
    }
    cout << "No solution." << endl;
}

int main() {

    std::ios::sync_with_stdio(false);

    int caseNum;
    cin >> caseNum;
    int counter = 1;
    bool firstTime = true;

    while (caseNum--) {
        
        num = 0;
        char c;
        for (int i = 0, index = 0; i < 7; ++i) {
             for (int j = 0; j < 7; ++j, ++index) {
                cin >> c;
                switch (c) {
                   case 'x' : pegs[index] = false; allow[index] = false; break;
                   case 'o' : pegs[index] = true;  allow[index] = true;  break;
                   case 'e' : pegs[index] = false; allow[index] = true;  break;
                   case 'O' : pegs[index] = true;  allow[index] = true;  last = index;
                      break;
                   case 'E' : pegs[index] = false; allow[index] = true;  last = index;
                      break;
                }
            if (pegs[index]) ++num;
            }
        }
        orig = num;
        next_peg = 0;
        next_dir = 0;
        cout << "Dataset " << counter++ << ":" << endl;
        go();
        cout << endl;
        firstTime = false;
    }

    return 0;
}