白駿バイナリゲーム(18112)

11893 ワード

バイナリゲーム
1.ヒント
1)バイナリ数の最大長は101010である.210=10242^{10}=1024210=1024であるため、これを頂点としてグラフィックナビゲーションアルゴリズムを適用することができる.
2)ビットマスクとxorにより,頂点間の移動を容易に実現できる.
2.近接
ヒントを参照
3.実施
public class Main {
	
	static int bfs(int u, int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(u);
		int[] dist = new int[1024];
		Arrays.fill(dist, -1);
		dist[u] = 0;
		while (!q.isEmpty()) {
			int here = q.poll();
			int range = 9;
			while (range - 1 >= 0 && (here & (1 << range)) == 0) range--;
			for (int i = 0; i < range; i++) {
				int there = here ^ (1 << i);
				if (dist[there] == -1) {
					q.offer(there);
					dist[there] = dist[here] + 1;
				}
			}
			if (here + 1 < 1024 && dist[here + 1] == -1) {
				q.offer(here + 1);
				dist[here + 1] = dist[here] + 1;
			}
			if (here - 1 >= 0 && dist[here - 1] == -1) {
				q.offer(here - 1);
				dist[here - 1] = dist[here] + 1;
			}
		}
		return dist[v];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int L = Integer.parseInt(br.readLine(), 2);
		int K = Integer.parseInt(br.readLine(), 2);
		System.out.println(bfs(L, K));
	}

}