1133: Knight Moves

题目意思是，以象棋中马字的方式行走，寻找从起点到终点的最短步数；

描述

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

输入

The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

输出

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

样例输入

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

样例输出

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

反思：

1.走马步是走八个方向，刚开始这个搞了好久，哈哈哈。

2.刚开始想用bfs写，并且自己清楚的记得bfs是最短路径常用的，方法，可以自己却忘记了为什么bfs可以用作最短路径，因为在一个地图中，bfs有点像扩散的形式，每一次往外扩散一圈，前一圈没有走完的话，后面一圈肯定不会走，因为队列的先进先出性质

3.遇到的另一个困难是，不知道怎么记录步数，利用一点点动态规划的思想，那么当前的步数，肯定是前一步的步数+1，那么可以利用一个二维数组来记录步数的信息，每个格子表示走到这个位置的最短步数（最短是因为bfs的属性）。

4.刚开始实在想不清楚bfs怎么走，那么我就写dfs，写dfs的时候细节上面有欠缺，找了半天，发现符号方向写反了，不过倒是锻炼了自己一层层找问题debug的能力，有好有坏吧，非要说，那全是好处，让我见识到了自己的蠢。

5.写完后发现，这个dfs也太慢了啊，虽然答案正确，但是要过一会才能够跳出来，我还特地用了可行性剪枝--当前路径已经大于最小路径时就return，可是还是超时。

1. ​DFS 的天然缺陷：无法保证首次找到最短路径

• BFS 按层遍历，首次到达终点的路径一定是最短路径，可以立即返回。
• DFS 会尝试所有可能的路径（包括绕远路的路径），直到找到终点，然后通过回溯继续搜索更短路径。即使已经找到一条路径，仍需遍历其他可能路径来确认最小值。
• ​时间复杂度：在最坏情况下，DFS 的时间复杂度达到指数级（例如骑士每步有 8 种选择，深度为 n 时复杂度为 O(8^n)）。而 BFS 的时间复杂度为 O(N^2)（N=8）。

2. ​缺乏高效剪枝

• 你虽然使用了 if (step > min_step) return; 进行剪枝，但：
  • ​初始 min_step 过大：如果初始值设为 INT_MAX，第一次找到的路径可能很长，后续才能逐步优化。
  • ​无法提前剪枝：在 DFS 中，即使某个位置已经被以更少的步数访问过，后续更长的路径仍会重复访问该位置。

3. ​重复访问同一位置

• 使用 visited 数组标记已访问的位置，但回溯时会取消标记​（visited[nx][ny] = false），导致同一位置可能被多次访问。
• ​例如：位置 (x, y) 可能被通过不同路径多次访问（如先通过 5 步到达，后又通过 3 步到达），而后者本应更优，但由于回溯机制，无法阻止无效的长路径继续搜索。

4. ​对比 BFS 的优化

• BFS 的 dist 数组记录了每个位置的最小步数，一旦一个位置被访问过，后续更长的路径会自动跳过该位置。
• 你的 DFS 实现没有类似的优化，导致大量重复计算。

改进建议

方案 1：改用 BFS

直接替换为 BFS，时间复杂度从指数级降至 O(N^2)（N=8），效率极快。

方案 2：优化 DFS（不推荐）

如果坚持用 DFS，可以引入记忆化剪枝：

cpp

// 记录到达每个位置的最小步数
vector<vector<int>> memo(N+1, vector<int>(N+1, INT_MAX));

void dfs(int sx, int sy, int ex, int ey, int step) {
    if (step >= memo[sx][sy]) return; // 当前路径步数不比已有记录更优，直接剪枝
    memo[sx][sy] = step; // 更新最小步数

    if (sx == ex && sy == ey) {
        min_step = min(min_step, step);
        return;
    }

    for (int i = 0; i < 8; i++) {
        int nx = sx + dx[i], ny = sy + dy[i];
        if (nx >= 1 && nx <= 8 && ny >= 1 && ny <= 8) {
            dfs(nx, ny, ex, ey, step + 1);
        }
    }
}

• ​优化效果：避免重复访问同一位置的长路径，但仍不如 BFS 高效。

性能对比

总结

DFS 不适合解决最短路径问题，尤其是当路径长度较大时。你的代码慢在 DFS 的指数级时间复杂度、重复访问和无效路径回溯。强烈建议改用 BFS，这是解决此类问题的标准方法。

代码：

#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<utility>

using namespace std;

const int N=8;

int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

struct Position{
    int x,y;
    Position(int x=0,int y=0):x(x),y(y){}
};


Position trans(string& s)
{
    return Position(s[0]-'a',s[1]-'1');
}

int bfs(Position& start,Position& end)
{
    if(start.x==end.x&&start.y==end.y)
    {
        return 0;
    }

    queue<Position> q;
    q.push(start);

    vector<vector<int>> dist(N,vector<int>(N,-1));
    dist[start.x][start.y]=0;

    while(!q.empty())
    {
        Position cur=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];

            if(nx>=0&&nx<N&&ny>=0&&ny<N&&dist[nx][ny]==-1)
            {
                dist[nx][ny]=dist[cur.x][cur.y]+1;
                if(nx==end.x&&ny==end.y)
                {
                    return dist[nx][ny];
                }
                q.push(Position(nx,ny));
            }
        }
    }

   
}


int main()
{
    string a,b;
    while(cin>>a>>b)
    {
        Position start=trans(a);
        Position end=trans(b);
        int count=bfs(start,end);
        cout<<"To get from "<<a<<" to "<<b<<" takes "<<count<<" knight moves."<<endl;
    }
}

记忆化剪枝挺有意思，保存状态，维持最优状态。