求x到y的最少计算次数

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

int x,y;

void BFS(){
    map<int,bool> vis;
    queue<pair<int,int>> q;
    q.push({x,0});
    vis[x] = false;
    while(!q.empty()){
        pair<int,int> p = q.front();
        q.pop();
        int t = p.first, cnt = p.second;
        if(t==y){
            cout<<p.second<<endl;
            return;
        }
        if(vis.find(t+1)==vis.end()){
            q.push({t+1, cnt+1});
            vis[t+1] = true;
        }
        if(vis.find(t-1)==vis.end()){
            q.push({t-1, cnt+1});
            vis[t-1] = true;
        }
        if(vis.find(2*t)==vis.end()){
            q.push({2*t, cnt+1});
            vis[2*t] = true;
        }
    }
}

int main(){
    scanf("%d,%d", &x, &y);
    BFS();
    return 0;
}

#bfs这是一个最小路径的搜索问题，第一时间想到这个，这里多加了一列用来储存位置

	

#include <iostream>
#include <deque>
#include <unordered_set>

using namespace std;

int breadth_first_search_algorithm(int s, int t) {
  deque<int> q{{s}};
  unordered_set<int> seen{s};
  
  int steps = 0;
  while (not q.empty()) {
    size_t s = q.size();
    while (s--) {
      const int curr = q.front(); q.pop_front();
      if (curr == t) return steps;
      for (const int nxt : {curr - 1 , curr + 1, curr << 1}) {
        if (!seen.emplace(nxt).second) continue;
        q.emplace_back(nxt);
      }
    }
    ++steps;
  }
  
  return -1;
}

int main(const int argc, const char* const argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int x, y;
  fscanf(stdin, "%d,%d", &x, &y);
  cout << breadth_first_search_algorithm(x, y);
  return 0;
}

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] nums = s.split(",");
        int a = Integer.parseInt(nums[0]);
        int b = Integer.parseInt(nums[1]);
        
        int ans = solution(a,b);
        System.out.println(ans);
    }
    
    private static int solution(int a, int b){
        
        int ans = 0;
        // 特殊值
            if(a == 0 && b <= 0) return Math.abs(b);
            if(a == 0 && b > 0) return minOps(1,b) + 1;

        // a b 同号
        if(a * b > 0){
            a = Math.abs(a); b = Math.abs(b);
            if(a >= b) return a - b;
            // a < b
            else return minOps(a,b);
        } 
        // a b 异号
        // 如果 a 是负值，将 a 转换为正值 1，则 a * b > 0,调用自身得到结果。
        if(a < 0) return ans - a + 1 + solution(1,b);
        // 如果 b 是负值，将 b 转换为正值 1。
        return ans - b + 1 + solution(a,1);
    }
    
    private static int minOps(int a, int b){

        if(b >= a && b <= (a << 1))
            return Math.min(b - a,(a << 1) - b + 1);
        if((b & 1) == 1)
            return Math.min(minOps(a,(b + 1) >> 1), minOps(a,(b - 1) >> 1)) + 2;
        return minOps(a,b >> 1) + 1;
    }
}

#include <bits/stdc++.h>
using namespace std;
int bfs(int x,int y,map<int,int> &m){
    queue<int> que;
    int sum=0;
    que.push(x);
    m.insert(make_pair(x,0));
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        if(temp>100||temp<-100)
            continue;
        sum=m[temp];
        if(temp==y){
            break;
        }
        if(m.find(temp+1)==m.end()){
            que.push(temp+1);
            m.insert(make_pair(temp+1,sum+1));
        }
        if(m.find(temp-1)==m.end()){
            que.push(temp-1);
            m.insert(make_pair(temp-1,sum+1));
        }
        if(m.find(temp*2)==m.end()){
            que.push(temp*2);
            m.insert(make_pair(temp*2,sum+1));
        }
    }
    return sum;
}
int main(){
    int x,y;
    scanf("%d,%d",&x,&y);
    map<int,int> m;
    cout<<bfs(x,y,m);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

map<int,int> dp;

int Min(int x, int y, int z, int k) {
	return min(min(x, k), min(y, z));
}

int main() {
	int x, y;
	scanf("%d,%d", &x, &y);
	for (int i = -400 ; i <= 400; i++) {
		dp[i] = 1000000;
	}
	dp[y] = 0;
	for (int i = 200; i >= -200; i--) {
		for (int j = 200; j >= -200; j--) {
			dp[j] = Min(dp[j - 1] + 1, dp[j + 1] + 1, dp[j * 2] + 1, dp[j]);
		}
	}
	cout << dp[x] << "\n";
	return 0;
}

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-09 18:27
 * @Description:
 * @version: 1.0
 */
public class Main {
    static Scanner sc = new Scanner(System.in);
    static String s[] = sc.next().split(",");
    static int x = Integer.valueOf(s[0]);
    static int y = Integer.valueOf(s[1]);
    static int min = Math.abs(x - y);//最小值的上界
    public static void main(String[] args) {
        dfs(x, y, 0);
        System.out.println(min);
    }

    private static void dfs(int x, int y, int count) {
        if (count == min)
            return;
        if (x == y){
            min = count;
            return;
        }
        dfs(x + 1, y, count + 1);
        dfs(x - 1, y, count + 1);
        dfs(x * 2, y, count + 1);
    }
}

-100,100怎么说？Java用BFS直接OOM

//本题不太适合用dfs，但看讨论里没有dfs写法，还是加一个；
#include <iostream>

using namespace std;

int result = 200;

void dfs(int x, int y, int step){

    if(step>result){
        return;
    }
    if(x==y){
        result = min(result, step);
        return;
    }

    if(x<y){
        dfs(x+1, y, step+1);
    }
    else{
        dfs(x-1, y, step+1);
    }
    dfs(2*x, y, step+1);

    return;
}

int main(){

    int x, y;
    char c;
    while(cin >> x >> c >> y){

        result = 200;
        dfs(x, y, 0);
        cout << result << endl;

    }
    return 0;
}

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author lihaoyu
 * @date 2019/12/28 14:21
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String next = scanner.next();
        int x = Integer.parseInt(next.split(",")[0]);
        int y = Integer.parseInt(next.split(",")[1]);
        if(y <= x){
            System.out.println( x - y);
            return;
        }
        if(y <= 0){
            System.out.println(Math.abs(x - y));
            return;
        }
        int count = 0;
        if( x <= 1){
            count += 1 - x;
            x = 1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(x);
        // 用来记录有没有出现过
        boolean[] flags = new boolean[101];
        while(true){
            // 先查一下有没有
            if(list.contains(y)){
                System.out.println(count);
                return;
            }
            int len = list.size();
            count++;
            for(int i = 0; i < len; i++){
                Integer temp = list.pollFirst();
                if(temp - 1 > 0 && temp - 1 <= 100 && !flags[temp-1]) {
                    list.addLast(temp-1);
                    flags[temp-1] = true;
                }
                if(temp + 1 > 0 && temp + 1 <= 100 && !flags[temp+1]) {
                    list.addLast(temp+1);
                    flags[temp+1] = true;
                }
                if(temp * 2 > 0 && temp * 2 <= 100 && !flags[temp*2]) {
                    list.addLast(temp*2);
                    flags[temp*2] = true;
                }
            }
        }

    }
}

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int main() {
    int x, y;
    int cnt = 0;
    bool flag = false;
    scanf("%d,%d", &x, &y);
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            int tmp = q.front();
            q.pop();
            if (tmp == y) {
                flag = true; 
                break;
            } else {
                q.push(tmp + 1);
                q.push(tmp - 1);
                q.push(tmp * 2);
            }
        }
        if (flag)
            break;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}