解题思路分析

1. 问题分析

这是一个典型的骑士巡游问题（Knight's Tour），要求找到骑士访问棋盘所有方格且不重复的路径。特殊要求：

• 棋盘尺寸不固定（p×q，最多26格）
• 需要输出字典序最小的路径
• 无解时输出"impossible"

2. 算法选择

深度优先搜索（DFS） + 回溯法：

• 使用DFS探索所有可能的路径
• 优先尝试字典序小的移动方向
• 找到第一条完整路径即可返回

3. 关键实现细节

1. 移动方向定义：

   const int go[8][2] = {
       {-2, -1},  // 方向1（最左上）
       {-2, 1},   // 方向2
       {-1, -2},  // 方向3
       {-1, 2},   // 方向4
       {1, -2},   // 方向5
       {1, 2},    // 方向6
       {2, -1},   // 方向7
       {2, 1}     // 方向8（最右下）
   };
   

   • 按字典序优先级排列方向（A1→B3比A1→C2优先）

2. DFS核心逻辑：

   • 标记已访问的方格
   • 记录路径
   • 尝试所有8个可能方向（按预定义顺序）
   • 回溯时取消标记

3. 字典序保证：

   • 从左上角(A1)开始
   • 方向数组按字典序优先级排序
   • 找到第一条完整路径即为字典序最小

4. 复杂度分析

• 时间复杂度：O(8^(p×q))（最坏情况）
• 空间复杂度：O(p×q)（存储访问标记和路径）

5. 优化策略

1. 提前终止：找到第一条路径立即返回
2. 可行性检查：
   • 1×1棋盘直接返回
   • 某些棋盘尺寸（如2×3）必然无解
3. 按字典序搜索：方向数组的顺序保证了最先找到的路径就是字典序最小的

6. 代码特点

• 使用全局变量简化参数传递
• flg标记是否已找到解
• 路径存储为坐标序列，最后转换为字母+数字格式

7. 边界情况处理

• 1×1棋盘：直接输出A1
• 无解情况：如2×3棋盘
• 最大尺寸：5×5（25格）或2×13（26格）

标程

#include <iostream>
#include <cstring>
using namespace std;
#define AUTHOR "HEX9CF"

const int go[8][2] = {
    {-2, -1},
    {-2, 1},
    {-1, -2},
    {-1, 2},
    {1, -2},
    {1, 2},
    {2, -1},
    {2, 1}};

int n, m;
int vis[30][30];
int path[30][2];
int flg;

void dfs(int x, int y, int s) {
    if(s == m * n) {
        flg = 1;
        return;
    }
    for(int i = 0; i < 8; i++) {
        int xx = x + go[i][0];
        int yy = y + go[i][1];
        if(xx > 0 && xx <= n && yy > 0 && yy <= m && !vis[xx][yy] && !flg) {
            vis[xx][yy] = 1;
            path[s][0] = xx;
            path[s][1] = yy;
            dfs(xx, yy, s + 1);
            vis[xx][yy] = 0;
        }
    }
    return;
}

int main() {
    int t;
    cin >> t;
    for(int cnt = 1; t--; cnt++) {
        cin >> m >> n; // 行 列
        cout << "Scenario #" << cnt << ":" << endl;
        flg = 0;
        memset(vis, 0, sizeof(vis));
        path[0][0] = 1;
        path[0][1] = 1;
        vis[1][1] = 1;
        dfs(1, 1, 1);
        if(flg) {
            for(int i = 0; i < n * m; i++) {
                cout << char(path[i][0] + 'A' - 1) << path[i][1];
            }
            cout << endl;
        } else {
            cout << "impossible" << endl;
        }
        cout << endl;
    }
    return 0;
}