C++14 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2019-04-07

#include<stdio.h>
int Minimum = 999999;
int dfs(int a,int b,int A,int B,int step){
    if(a>A || b>B){
        return -1;
    }
    if(step>Minimum){
        return -1;
    }
    if((A==a && b!=B )||(B==b && a!=A)){
        return -1;
    }
    if(a==A && b==B){
        if(step<Minimum && step>=0){
            Minimum = step;
        }
    }
    dfs(a*2,b*2,A,B,step+1);
    dfs(a+1,b+1,A,B,step+1);
    return -1;
}
int main(){
    int a,b,A,B;
    scanf("%d%d%d%d",&a,&b,&A,&B);
    int res = dfs(a,b,A,B,0);
    if(Minimum!=999999){
        printf("%d\n",Minimum);
    }else{
        printf("-1\n");
    }
    return 0;
}

Rust 解法, 执行用时: 3ms, 内存消耗: 328KB, 提交时间: 2020-08-16

use std::str::FromStr;

fn min_times(a: usize, b: usize, A: usize, B: usize, times: usize) -> (bool, usize) {
    if a > A || b > B {
        (false, times)
    } else if a == A && b == B {
        (true, times)
    } else {
        let (is_success, times1) = min_times(a + 1, b + 1, A, B, times);
        if is_success {
            (true, times1 + 1)
        } else {
            let (is_success, times2) = min_times(a * 2, b * 2, A, B, times);
            (is_success, times2 + 1)
        }
    }
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf);
    let mut nums = buf.trim_end().split(' ').map(usize::from_str).flatten();
    let (a, b, A, B) = (
        nums.next().unwrap(),
        nums.next().unwrap(),
        nums.next().unwrap(),
        nums.next().unwrap(),
    );
    let (is_success, times) = min_times(a,b,A,B,0);
    if is_success {
        println!("{}", times);
    }else{
        println!("-1");
    }
}

C 解法, 执行用时: 3ms, 内存消耗: 352KB, 提交时间: 2022-07-29

#include<stdio.h>
#include<stdlib.h>
int main() {
    int a=0,b=0,A=0,B=0,i=1,p=1,fnum,lnum,aa=0;
	scanf("%d%d%d%d",&a,&b,&A,&B);
	if(A<a||B<b){
        printf("-1");
        }
    else{
        while(i++){
            if(aa<0){
            printf("-1");
            break;
            }
            if(aa==B-b*p/2){
            fnum=i-3;
            break;
            }
            aa=A-a*p;
            p=p*2;
        }
        if(aa!=0){
            for(i=0,lnum=0;aa!=0;i++){
                if(aa%2==0&&lnum<fnum){
                    aa=aa/2;
                    lnum++;
                }
                else{
                    aa--;
                }
            }
            printf("%d\n",i);
        }
        else{
            printf("%d\n",fnum);
        }
    }
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2020-07-05

#include <stdio.h>
#include <stdlib.h>

int min(int a,int b)
{
	if(a==-1&&b==-1)
		return -1;
	if(a==-1&&b!=-1)
		return b;
	if(b==-1&&a!=-1)
		return a;

	return a>b?b:a;
}
int dfs(int a,int b,int A,int B,int nums)
{
	if(a>A||b>B)
		return -1;
	if(a==A&&b==B)
	{
		return nums;
	}
	else
	{
		nums++;
//		;
//		;
		return min(dfs(a+1,b+1,A,B,nums),dfs(a*2,b*2,A,B,nums));
	}
}

int main(void) {
	int a,b,A,B;
	scanf("%d %d %d %d",&a,&b,&A,&B);
//	a=100;
//	b=1000;
//	A=202;
//	B=2002;
	printf("%d",dfs(a,b,A,B,0));
}

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-06-13

#include <vector>
#include <iostream>
#include <limits.h>
using namespace std;
int trans( int a, int b,  int A,  int B, vector<vector<int>> &dp){
    if(A>=a && B>=b && dp[A-a][B-b] != INT32_MAX) return dp[A-a][B-b];
     int ret = INT32_MAX;
    if(a == A && b == B) return 0;
    if(a > A && b >B) return -1;
    if( A % 2 == 0 && B % 2 ==0){
         int ret1 = trans(a, b, A - 1, B - 1, dp);
        if(ret1 != -1) {
            if(A > a && B> b) dp[A-1-a][B-1-b] = ret1;
            ret = min(ret, ret1 + 1);

        }
        int ret2 = trans(a, b, A / 2, B / 2, dp);
        if(ret2 != -1){
            if(A/2 >= a && B/2 >= b) dp[A/2-a][B/2-b] = ret2;
            ret = min(ret, ret2 + 1);
        } 
    }else{
        int ret3 = trans(a, b, A - 1, B-1, dp) ;
        if(ret3 != -1) {
            if(A > a && B> b) dp[A-1-a][B-1-b] = ret3;
            ret = min(ret, ret3 + 1);
        }
    }
    if(ret == INT32_MAX) ret = -1;
    if(A>=a && B>=b) dp[A-a][B-b] = ret;
    return ret;
}
int main(){
     int a,b,A,B;
    while(cin >> a >> b >> A >> B){
        if(A-a<0 || B-b<0){
            cout << -1 << endl;
            continue;
        }
        vector<vector<int>> dp(A+1 - a, vector<int>(B+1 - b, INT32_MAX));
        cout << trans(a, b, A, B, dp) << endl;
    }
    return 0;
}