【第63题】广度优先搜索(BFS)6连刷(三): 马的遍历

#include <bits/stdc++.h>
using namespace std;

int a[403][403];
int n, m;
int b[403][403];

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

bool is (int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m) && !b[x][y];
}

struct edge {
    int x, y;
};

queue<edge> v;

void bfs(int x, int y ) {
    v.push({x, y});
    while (!v.empty()) {
        edge k = v.front();
        v.pop();
        for (int i = 0; i < 8; ++i) {
            if(is(k.x + dx[i], k.y + dy[i])) {
                v.push({k.x + dx[i], k.y + dy[i]});
                b[k.x + dx[i]][k.y + dy[i]] = true;
                a[k.x + dx[i]][k.y + dy[i]] = a[k.x][k.y] + 1;
            }
        }
    }
}

int main () {
    int x, y;
    cin >> n >> m >> x >> y;
    --x;
    --y;
    b[x][y] = true;
    bfs(x, y);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!b[i][j]) {
                cout << -1 << " ";
                continue;
            }
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}