[Algorithm]¥ٵٵٵٵB

14789 ワード
白駿 BFS テキストリンク

0、問題


整数AをBに変えたいです.可能な演算は次の2つです.
2を掛ける.
数の一番右に1を追加します.
AからBまでの演算の最大値を求める.
入力
第1行は、A、B(1≦Aしゅつりょく
AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.

1.アイデア


💡 BFS
💡 キューを使用して2つの演算を実行する場合は、B以下の数をキューに入れます.
💡 キュー内の数値がBに等しい場合、その数値が返されます.
💡 キュー内の数字がすべて表示されますが、Bと等しくない場合は-1を返します.

2.コア解答

  • キューを使用して2つの演算が実行される場合、B以下の数
    • がキューに追加される.
    if(cur.num*2 <= B) {
	q.add(new Cal(cur.num*2, cur.cnt+1));
}
if(cur.num*10+1 <= B) {
	q.add(new Cal(cur.num*10+1, cur.cnt+1));
}
  • キュー内の数字がBに等しい場合、その数字
    • が戻る.
    if(cur.num == B) 
	return cur.cnt+1;
  • キューに数字が表示されますが、Bと等しくない場合は、-1
    • に戻ります.
    while(!q.isEmpty()){
...
}

return -1;

    3.コード

    import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Bruteforce_8 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		
		long A = Long.parseLong(s[0]);
		long B = Long.parseLong(s[1]);
		
		System.out.println(bfs(A,B));
	}

	static int bfs(long A, long B) {
		Queue<Cal> q = new LinkedList<>();
		q.add(new Cal(A,0));
		
		while(!q.isEmpty()) {
			Cal cur = q.poll();
			
			if(cur.num == B) 
				return cur.cnt+1;
			
			if(cur.num*2 <= B) {
				q.add(new Cal(cur.num*2, cur.cnt+1));
			}
			if(cur.num*10+1 <= B) {
				q.add(new Cal(cur.num*10+1, cur.cnt+1));
			}
		}
		
		return -1;
	}
	
	static class Cal{
		long num;
		int cnt;
		Cal(long num, int cnt){
			this.num = num;
			this.cnt = cnt;
		}
	}
}

    4.結果



    成功
    あまり時間がかからなかったので、2回間違えました.😥
    Node.jsパッケージマネージャ-pm 2(8)
    プログラム設計アルゴリズムの問題.JavaScript