当前位置：首页 > news >正文

魔法数字（dfs/bfs）

news 来源：原创 2024/5/5 16:33:25

传送门

题意：

一天，牛妹找牛牛做一个游戏，牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。操作共有三种，如下：

在当前数字的基础上加一，如：4转化为5
在当前数字的基础上减一，如：4转化为3
将当前数字变成它的平方，如：4转化为16

输入：

给定n,m,分别表示牛牛和牛妹的数字。

输出：

返回最少需要的操作数。

方法一(bfs)

每个数字可以看做一种状态，那么本题可以看做隐式图的最短路，考虑 $b f s$ ，直接遍历所有的情况，第一次到达 $m$ 时就是最少的操作次数

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;

int d[maxn];
queue<int> q;

int solve(int n,int m){
    memset(d,0,sizeof d);
    if(n>=m) return n-m;
    q.push(n);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(u==m) return d[m];
        if(u<m){
            if(!d[u+1]) q.push(u+1),d[u+1]=d[u]+1;
            if(!d[u*u]) q.push(u*u),d[u*u]=d[u]+1;
        }
        if(u>1 && !d[u-1]) q.push(u-1),d[u-1]=d[u]+1;
    }
    return d[m];
}

int main(){
    int n,m;
    while(cin>>n>>m){
        cout<<solve(n,m)<<endl;
    }
    return 0;
}

方法二(dfs)

实际上只需在 $d f s$ 过程中分情况考虑：

若 $\geq m$ ，那么只能每次减少直到为m
否则就找到 $n$ 的附近的两个数 $i, j$ ，使得 $\leq m,j*j \geq m$ ，因为此时已经是接近 $m$ 的数了，无论如何也不会再开方了，那么只需递归到 $n, i$ 或 $n, j$ ，找到最小的操作次数即可

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;

inline int min(int &x,int &y){
    return x>y?y:x;
}

int dfs(int n,int m){
    if(n>=m){
        return n-m;
    }else{
        int x=n*n;
        if(x==m) return 1;
        if(x>m){
            int i=n,j,k,res;
            while(i*i>m){
                j=i;
                i--;
            }
            if(j*j-m>m-i*i){
                k=i;
                res=m-i*i;
            }else{
                k=j;
                res=j*j-m;
            }
            return min(m-n,dfs(n,k)+1+res);
        }else{
            int i=n,j,k,res;
            while(i*i<m){
                j=i;
                i++;
            }
            if(i*i-m>m-j*j){
                k=j;
                res=m-j*j;
            }else{
                k=i;
                res=i*i-m;
            }
            return min(m-n,dfs(n,k)+1+res);
        }
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        cout<<dfs(n,m)<<endl;
    }
    return 0;
}