白駿バイナリゲーム(18112)
11893 ワード
バイナリゲーム
1.ヒント
1)バイナリ数の最大長は101010である.210=10242^{10}=1024210=1024であるため、これを頂点としてグラフィックナビゲーションアルゴリズムを適用することができる.
2)ビットマスクとxorにより,頂点間の移動を容易に実現できる.
2.近接
ヒントを参照
3.実施
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));
}
}
Reference
この問題について(白駿バイナリゲーム(18112)), 我々は、より多くの情報をここで見つけました https://velog.io/@axiom0510/b18112テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol