A Knight's Journey

GitHub返回列表

OJ: OpenJ_Bailian

题目 ID: 2488

标签: dfs

日期: 2026-01-20 19:54

目录

  1. 1. 核心难点解析
  2. 2. 贪心策略：确定 8 个方向的顺序
  3. 3. 算法步骤 (DFS + 回溯)
  4. 4. 逻辑实现伪代码
  5. 5. 注意事项
  6. 代码

这道题目是一个经典的骑士巡逻问题（Knight’s Tour Problem）的变体。它的核心要求是：在给定的 p×qp \times q 棋盘上，寻找一条路径，使骑士恰好访问每个方格一次，并要求输出字典序最小的路径。

题目的难点在于 字典序, 你自己画个图就知道了

1. 核心难点解析

  • 字典序最小（Lexicographically Smallest）：

    这是本题的关键。棋盘的坐标表示为“字母+数字”（如 A1, B2）。字典序比较时，先比字母，再比数字。

    • 起点选择：为了让路径字典序最小，必须从 A1 开始。因为任何从 B1 或 A2 开始的路径，其首字符在字典序上都大于 A1。
    • 移动顺序：在 DFS（深度优先搜索）过程中，骑士有 8 个可选方向。为了保证找到的第一条完整路径就是字典序最小的，我们需要按照特定的顺序尝试这 8 个方向。

2. 贪心策略：确定 8 个方向的顺序

假设当前坐标为 (col,row)(col, row)，其中 colcol 代表字母（A, B…），rowrow 代表数字（1, 2…）。我们需要按照 colcol 增量优先、再看 rowrow 增量的原则排序：

  1. col−2,row−1col-2, row-1 (例如：从 C3 移动到 A2)
  2. col−2,row+1col-2, row+1
  3. col−1,row−2col-1, row-2
  4. col−1,row+2col-1, row+2
  5. col+1,row−2col+1, row-2
  6. col+1,row+2col+1, row+2
  7. col+2,row−1col+2, row-1
  8. col+2,row+1col+2, row+1

严格遵守这个顺序进行 DFS，找到的第一组解即为最优解。

3. 算法步骤 (DFS + 回溯)

  1. 初始化：
    • 读取测试用例数量 nn。
    • 对于每个用例，创建一个 p×qp \times q 的标记数组 visited，记录方格是否走过。
    • 设定总步数目标为 p×qp \times q。
  2. 搜索 (DFS)：
    • 从 A1 (即坐标 (1, 1)) 开始搜索。
    • 标记当前格为已访问，并存入路径序列。
    • 递归基准：如果路径长度等于 p×qp \times q，说明已遍历全图，返回成功。
    • 尝试移动：按照上述 8 个方向的顺序依次尝试。
    • 检查合法性：目标格必须在棋盘内且未被访问。
    • 回溯：如果某个分支走不通，撤销标记，尝试下一个方向。
  3. 输出：
    • 如果 DFS 找到解，输出路径。
    • 如果 DFS 遍历完所有可能仍未找到解，输出 impossible。

4. 逻辑实现伪代码

cpp
// 8个方向的偏移量 (注意顺序：先看col位移，再看row位移)
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

bool dfs(int x, int y, int step) {
    if (step == p * q) return true; // 找齐了

    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 1 && nx <= q && ny >= 1 && ny <= p && !vis[ny][nx]) {
            vis[ny][nx] = true;
            path[step] = {nx, ny}; // 记录路径
            if (dfs(nx, ny, step + 1)) return true;
            vis[ny][nx] = false; // 回溯
        }
    }
    return false;
}

5. 注意事项

  • 行列混淆：题目中 pp 是数字（行），qq 是字母（列）。通常我们习惯 (x,y)(x, y)，这里建议明确 xx 对应列（A, B, C…），yy 对应行（1, 2, 3…）。
  • 棋盘大小：p×q≤26p \times q \le 26 是个很小的范围，这意味着简单的 DFS 不会超时，不需要使用复杂的优化算法（如 Warnsdorff’s rule）。
  • 不可能的情况：某些尺寸的棋盘（如 3×33 \times 3, 2×32 \times 3 等）是无法完成全巡逻的，DFS 会自然返回失败。

代码

cpp
#include <iostream>
#include <cstring>

using namespace std;

// 全局变量定义
int P, Q;               // P 为行数(1..p), Q 为列数(A..q)
bool visited[30][30];    // 标记是否访问过
struct Node {
    int x, y;           // 存储路径坐标
} path[30];

// 核心：方向数组必须按照字典序排列
// 规则：优先尝试字母小的(dx小)，字母相同时尝试数字小的(dy小)
// 字母偏移 dx: -2, -2, -1, -1,  1,  1,  2,  2
// 数字偏移 dy: -1,  1, -2,  2, -2,  2, -1,  1
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};

bool finished = false;

/**
 * DFS 搜索函数
 * @param currX 当前列坐标 (对应字母)
 * @param currY 当前行坐标 (对应数字)
 * @param step  当前步数
 */
void dfs(int currX, int currY, int step) {
    path[step].x = currX;
    path[step].y = currY;

    if (step == P * Q) {
        finished = true;
        return;
    }

    for (int i = 0; i < 8; ++i) {
        int nextX = currX + dx[i];
        int nextY = currY + dy[i];

        // 检查边界及访问情况
        if (nextX >= 1 && nextX <= Q && nextY >= 1 && nextY <= P && !visited[nextY][nextX] && !finished) {
            visited[nextY][nextX] = true;
            dfs(nextX, nextY, step + 1);
            // 回溯
            if (!finished) {
                visited[nextY][nextX] = false;
            }
        }
    }
}

void solve(int caseNum) {
    cin >> P >> Q;
    
    // 初始化
    memset(visited, false, sizeof(visited));
    finished = false;

    // 字典序最小路径必然从 A1 (1, 1) 开始
    visited[1][1] = true;
    dfs(1, 1, 1);

    cout << "Scenario #" << caseNum << ":" << endl;
    if (finished) {
        for (int i = 1; i <= P * Q; ++i) {
            // 将数字坐标转回字母和数字形式
            // path[i].x 为列(字母), path[i].y 为行(数字)
            char col = (char)(path[i].x + 'A' - 1);
            cout << col << path[i].y;
        }
        cout << endl;
    } else {
        cout << "impossible" << endl;
    }
    cout << endl; // 每个测试用例后跟一个空行
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) {
        solve(i);
    }
    return 0;
}
python
import sys

def solve():
    # 读取输入
    try:
        line = sys.stdin.read().split()
        if not line: return
        n = int(line[0])
        cases = []
        for i in range(n):
            cases.append((int(line[i*2+1]), int(line[i*2+2])))
    except EOFError:
        return

    # 定义 8 个方向：严格按字典序（列增量优先，行增量次之）
    # dx: 列(字母)位移, dy: 行(数字)位移
    directions = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), 
                  (1, -2), (1, 2), (2, -1), (2, 1)]

    for i, (P, Q) in enumerate(cases, 1):
        visited = [[False] * Q for _ in range(P)]
        path = []

        def dfs(r, c):
            path.append(f"{chr(ord('A') + c)}{r + 1}")
            visited[r][c] = True
            
            if len(path) == P * Q:
                return True
            
            for dc, dr in directions:
                nc, nr = c + dc, r + dr
                if 0 <= nr < P and 0 <= nc < Q and not visited[nr][nc]:
                    if dfs(nr, nc):
                        return True
            
            # 回溯
            visited[r][c] = False
            path.pop()
            return False

        print(f"Scenario #{i}:")
        # 始终从 A1 (0, 0) 开始以保证字典序最小
        if dfs(0, 0):
            print("".join(path))
        else:
            print("impossible")
        print() # 每个 Case 后面的空行

if __name__ == "__main__":
    solve()