【bfs】洛谷 P1443 马的遍历

题目：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

记录一下第一道ac的bfs，原理是利用队列queue记录下一层的所有点，然后一层一层遍历；

其中：

1.pair<,>可以将两个数据类型压缩成一个数据压进队列里，在表示二维坐标时好用。

2.setw()可以设置输出的宽度，left可以设置为左对齐。

代码：

#include <iostream>

#include <queue>

#include <iomanip>

using namespace std;

typedef long long ll;

queue<pair<int, int>> a;

ll f[500][500], vis[500][500];

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

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

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int n, m, x, y;

    cin >> n >> m >> x >> y;

    for (int i = 1; i <= n; ++i)

    {

        for (int j = 1; j <= m; ++j)

        {

            f[i][j] = -1;

        }

    }

    f[x][y] = 0;

    vis[x][y] = 1;

    a.push(make_pair(x, y));

    while (!a.empty())

    {

        int xx = a.front().first, yy = a.front().second;

        a.pop();

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

        {

            int xxx = xx + dx[i], yyy = yy + dy[i];

            if (xxx < 1 || xxx > n || yyy < 1 || yyy > m || vis[xxx][yyy])

                continue;

            f[xxx][yyy] = f[xx][yy] + 1;

            a.push(make_pair(xxx, yyy));

            vis[xxx][yyy] = 1;

        }

    }

    for (int i = 1; i <= n; ++i)

    {

        for (int j = 1; j <= m; ++j)

        {

            cout << left << setw(5) << f[i][j];

        }

        cout << endl;

    }

    return 0;

}

巴特西

【bfs】洛谷 P1443 马的遍历

最新文章

热门文章