UVA439 Knight Moves

题目大意

有一个骑士，他可以骑马日字型跳跃，问他从A点到B点最少要几步

解题思路

这题就是一个特别裸的广搜板子

它的主要问题在于输入输出

输入的数据我们可以用\(pair\)读入，第一关键字存行(a~e)，第二关键字存列(1 ~ 8)

然后我们为了方便处理，把行也映射成数组1 ~ 8

所以有了我们的读入代码

预编译指令

#define x first

#define y second

定义的\(A, B\)

pair<char, int> A, B;

while (cin >> A.x >> A.y >> B.x >> B.y)

    {

        int sx = A.x - 'a' + 1, sy = A.y,

            fx = B.x - 'a' + 1, fy = B.y;

		//printf这句是输出

然后就是巨坑无比的输出了

一定要有句号！！！！！！！！！

代码

#include <iostream>

#include <cstring>

#include <queue>

#define x first

#define y second

using namespace std;

struct Point

{

    int x, y, dist;

    Point(int a = 0, int b = 0, int c = 0) : x(a), y(b), dist(c) {}

} ;

pair<char, int> A, B;

int mp[9][9];

int bfs(int& sx, int& sy, int& fx, int& fy)

{

    if (sx == fx && sy == fy) return 0;

    queue<Point> q;

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

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

    q.push(Point(sx, sy, 0));

    while (q.size())

    {

        Point t = q.front(); q.pop();

        for (int i = 0; i < 8; i ++ )

        {

            int x = t.x + dx[i], y = t.y + dy[i];

            if (x < 1 || x > 8 || y < 1 || y > 8) continue ;

            if (mp[x][y]) continue ;

            Point now = Point(x, y, t.dist + 1);

            if (now.x == fx && now.y == fy) return now.dist;

            q.push(now);

        }

    }

}

int main()

{

    while (cin >> A.x >> A.y >> B.x >> B.y)

    {

        int sx = A.x - 'a' + 1, sy = A.y,

            fx = B.x - 'a' + 1, fy = B.y;

        printf("To get from %c%d to %c%d takes %d knight moves.\n",

                A.x, A.y, B.x, B.y, bfs(sx, sy, fx, fy));

    }

    return 0;

}

巴特西

UVA439 Knight Moves

题目大意

解题思路

代码

Accepted!

最新文章

热门文章