[ABC272D] Root M Leaper 题解

DYYqwq · 2023-02-15 15:01:16 · 题解

题意

你每步可以走 \sqrt{M} 格。求问对于点 (i , j) 最少走多少步，若走不到，输出 -1。

Solution

很明显，这是一道 dfs 或 bfs，但是 dfs 会重复算很多遍，时间复杂度是错的，所以只能用 bfs。

根据题目， \sqrt{M} 格指的是欧几里得距离，即

我们不需要对于每个节点都计算出可以向哪里走，只需要一个初始化算出 dfs 或 bfs 模板中所需的偏移量 dx dy。那究竟怎么办呢？我们就假设我们处在 (0 , 0) 点，那原方程就变为了：

那我们直接 O(n^2) 枚举 k,l ，判断 k ^ 2 + l ^ 2 是否为 M，将 k,l 记录下来， 接着找就可以了。

如果有和我一样不知道为啥接着找而不是 break 的同学，看这里。

那还有一个问题，万一我找不到怎么办？没有符合要求的 k,l 怎么办？比如说 M = 6 的情况？显然，你就一步都走不出去了，所以除了第 1 个点输出 0 之外，其他点都无法到达，输出 -1。

记录完 k,l 即偏移量 dx dy 后，就是正常的 bfs 了，没什么可说的，直接上代码：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x , y;
};
queue<node> q;
int n , m;
bool flag = false; // 是否能走出去
int a , b;
int cnt = 0; // 每一步有几种走法
int dx[100010] , dy[100010]; // 偏移量，100000个 应该够了吧
int ans[410][410]; // 走到每个点所需的最小步数
bool in(int x , int y) // 是否在边界内
{
    return x <= n && x >= 1 && y <= n && y >= 1;
}
void bfs() // 正常bfs，不解释
{
    q.push({1 , 1});
    ans[1][1] = 0;
    while(!q.empty())
    {
        node tmp = q.front();
        q.pop();
        for(int i = 1 ; i <= cnt ; i ++)
        {
            int nx = tmp.x + dx[i];
            int ny = tmp.y + dy[i];
            if(in(nx , ny) && ans[nx][ny] > ans[tmp.x][tmp.y] + 1)
            {
                ans[nx][ny] = ans[tmp.x][tmp.y] + 1;
                q.push({nx , ny});
            }
        }
    }
}
void init() // 每一步的走法
{
    // x+ , y+
    dx[++ cnt] = a;
    dy[cnt] = b;

    // x+ , y-
    dx[++ cnt] = a;
    dy[cnt] = -1 * b;

    // x- , y+
    dx[++ cnt] = -1 * a;
    dy[cnt] = b;

    // x- , y-
    dx[++ cnt] = -1 * a;
    dy[cnt] = -1 * b;
}
int main()
{
    scanf("%d%d" , &n , &m);
    for(int i = 0 ; i <= n ; i ++)
    {
        for(int j = 0 ; j <= n ; j ++)
        {
            if(i * i + j * j == m)
            {
                a = i; // 行数 + a
                b = j; // 列数 + b
                init(); // 进行dx,dy的
                flag = true; // 有可以走的地方啦qwq
            }
        }
    }
    if(!flag) // 走不出去力（悲
    {
        for(int i = 1 ; i <= n ; i ++)
        {
            for(int j = 1 ; j <= n ; j ++)
            {
                if(i == 1 && j == 1) printf("0 "); // 初始点
                else printf("-1 "); // 除了初始点，都是-1
            }
            printf("\n");
        }
        return 0;
    }
    memset(ans , 0x3f , sizeof(ans));
    ans[1][1] = 0;
    bfs();
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= n ; j ++)
            printf("%d " , ans[i][j] == 0x3f3f3f3f ? -1 : ans[i][j]); // 有的地方由于特殊原因哪怕可以走，也到不了，所以需要特判一下qwq
        printf("\n");
    }
    return 0;
}