题解 SP12323 【NAKANJ - Minimum Knight moves !!!】

· · 题解

本题dfs&bfs做法

前面只有一位大佬写了双向bfs做法，蒟蒻的我在这里提供两种做法（常规bfs&dfs）

题意

给定T组起点，终点和坐标偏移量，求最少需要多少步从起点走到到终点

方法：

很容易看出来，这道题要使用搜索，bfs和dfs均可，这里提供这两种方法

bfs思路：

从起点开始一层一层搜索，第一次搜到终点就得到了最优解，直接返回+输出

dfs思路：

从起点开始重复执行八个方向的搜索，搜到终点就更新答案。但是，这样很明显会TLE，所以我设置了阈值，阈值设成8就可以过全靠数据弱

Code：

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

char s1, s2, e1, e2;
int N, sx, sy, ex, ey, cnt[110][110] = { 0 }, dx[10] = { 0,1,2,2,1,-1,-2,-2,-1,0 }, dy[10] = { 0,2,1,-1,-2,-2,-1,1,2,0 }, minn;
bool vis[110][110] = { false };

void dfs(int x, int y, int stp)//dfs
{
    if (x < 1 || y < 1 || x>8 || y>8 || stp > minn) return;//越界或者当前已经大于最优解，返回
    if (x == ex && y == ey) minn = min(minn, stp);//到达终点，更新答案
    else
        for (int i = 1; i <= 8; i++)
            dfs(x + dx[i], y + dy[i], stp + 1);//继续深搜
}

int bfs()//bfs
{
    queue<pair<int, int> >Q;//存点用的队列
    Q.push(make_pair(sx, sy));//压入起点
    vis[sx][sy] = true, cnt[sx][sy] = 0;//标记起点，标记为走过，步数为0
    while (!Q.empty())//循环直到队空
    {
        int nowx = Q.front().first, nowy = Q.front().second;//取队头
        if (nowx == ex && nowy == ey) return cnt[nowx][nowy];//到达终点，返回
        for (int i = 1; i <= 8; i++)
        {
            int newx = nowx + dx[i], newy = nowy + dy[i];//扩展新点
            if (newx >= 1 && newy >= 1 && newx <= 8 && newy <= 8 && !vis[newx][newy])
            {//如果不越界，没走过
                Q.push(make_pair(newx, newy));//压入新点
                vis[newx][newy] = true, cnt[newx][newy] = cnt[nowx][nowy] + 1;//标记新点
            }
        }
        Q.pop();//弹队头
    }
    return -1;//到不了
}

int main()
{
    cin >> N;//N组数据
    while (N--)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(vis, false, sizeof(vis));//初始化
        cin >> s1 >> s2 >> e1 >> e2;
        sx = s1 - 96, sy = s2 - 48, ex = e1 - 96, ey = e2 - 48;//利用ASCLL码得到起点，终点坐标
        /*minn = 8;//dfs把阈值设成8就能过
        dfs(sx, sy, 0);
        cout << minn << endl;*/
        cout << bfs() << endl;
    }
    return 0;
}

经过我多次实验，dfs阈值最少可以是6

数据：

bfs：20ms / 4.70MB / 1.36KB C++

dfs：

阈值8：740ms / 4.60MB / 1.36KB C++

阈值6：380ms / 4.50MB / 1.36KB C++

两种较简单的方法解析，求管理大大给过