洛谷-P1443 马的遍历

洛谷

原题链接

题目描述

有一个 n×mn \times mn×m 的棋盘，在某个点 (x,y)(x, y)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n,m,x,y$

输出格式

一个 $n\times m$ 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 5 格，不能到达则输出 −1）。
输入输出样例

输入 #1

3 3 1 1

输出 #1

0    3    2    
3    -1   1    
2    1    4    

说明/提示

数据规模与约定

对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$

算法1

结果

(BFS) $O(n)$

从当前位置出发能到达的所有点的坐标入队，并记录步数。
递推至队空也就是说，没有位置可以再走了，或者都已经走过了。

关于DFS和BFS

BFS专门用于解决求两点之间最短路的问题，而DFS是用来解决求一个点到另一个点路径总数的问题。

C++ 代码

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <iostream>
#include <algorithm>
#define ios ios::sync_with_stdio(false), cin.tie(0)
#define sd(n) scanf("%d", &n)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define fs first
#define se second
#define debug(x) cout << #x << ": " << x << endl
#define MOD 1000000007
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int N = 1e3 + 10;
int n, m, x, y, ans[N][N];
bool st[N][N];
int mx[9] = {0,-1,-2,-2,-1,1,2,2,1} ,my[9] = {0,-2,-1,1,2,2,1,-1,-2};
queue<int> qx, qy, qs;
/*
    对当前位置能到达的所有点的坐标入队，并记录步数。
    递推至队空也就是说，没有位置可以再走了，或者都已经走过了。
*/
inline void check(int num) //输出
{
    cout << num;
    if(num >= 10000) ;
    else if(num >= 1000) cout << " ";
    else if(num >= 100) cout << "  ";
    else if(num >= 10) cout << "   ";
    else if(num >= 0) cout << "    ";
    else if(num == -1) cout << "   ";
}
void bfs()
{
    while(!qx.empty())
    {
        int a = qx.front();
        int b = qy.front();
        int t = qs.front();
        ans[a][b] = t;
        qx.pop();qy.pop();qs.pop();
        rep(i, 1, 8)
        {
            if(a + mx[i] >= 1 && a+mx[i] <= n && b+my[i] >= 1 && b+my[i] <= m && !st[a+mx[i]][b+my[i]])
            {
                st[a + mx[i]][b + my[i]] = 1;
                qx.push(a + mx[i]);
                qy.push(b + my[i]);
                qs.push(t + 1);
            }
        }
    }
}
int main()
{
    ios;
    cin >> n >> m >> x >> y;
    memset(ans, -1 , sizeof ans);
    st[x][y] = 1;
    qx.push(x);
    qy.push(y);
    qs.push(0);
    bfs();
    rep(i, 1, n)
    {    
        rep(j ,1, m)    check(ans[i][j]);
        cout << endl;
    }
    return 0;
}