poj-1915-Knight Moves(入门BFS)

发布于 2019-07-21  994 次阅读


题目传送门:

题意:

求一个棋子从一个位置到另一个位置的所需要的做小步数。

棋子每一步有 8 个选择

分析:

很明显,是一个简单的BFS,把每一步的8个选择加入队列。

直到下一步是终点。

代码:

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 300+5;

int Next[8][2]={{-2,-1},{-1,-2},{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1}};
int vis[MAXN][MAXN];

struct Node
{
    int x, y, step;
};
Node t;
queue <Node> q;

void BFS(int sx, int sy, int ex, int ey, int n)
{
    Node head;
    t.x = sx, t.y = sy, t.step = 0;
    q.push(t);
    vis[sx][sy] = 1;
    while (!q.empty())
    {
        head = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            t.step = head.step + 1;
            t.x = head.x + Next[i][0];
            t.y = head.y + Next[i][1];
            if (t.x < 0 || t.y < 0 ||t.x>=n || t.y>=n || vis[t.x][t.y])
                continue;
            if (t.x == ex && t.y == ey)
            {
                cout << t.step << endl;
                return ;
            }
            vis[t.x][t.y] = 1;
            q.push(t);
        }
    }
    return ;
}

int main()
{
    int T, sx, sy, ex, ey, n;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                vis[i][j] = 0;
        while (!q.empty()) q.pop();
        cin >>  sx >> sy >> ex >> ey;
        if (sx == ex && sy == ey)
            cout << "0" << endl;
        else
            BFS(sx,sy,ex,ey,n);
    }

    return 0;
}

Simple And Clear