[白駿9019]DSLR
DSLR
ある行為が存在し、これらの行為を組み合わせたときに最短時間/最小時間を得る必要がある場合、BFSが考えられる.
図形では、頂点はある状態を表し、幹線は状態の変化を表す.BFSは起点から別の状態までの最短距離を求めるアルゴリズムであるからである.
この問題について.
この問題では、最小限のコマンドにナビゲートし、再構築する必要があります.これを実現する方法はいくつかあるかもしれませんが、私が使用する方法は、アクセス頂点を単純な
booleanとして表すのではなく、どの頂点からのアクセスを記録するかです.(実は、他の方法を考えたことはありませんが...)BFSは実施しやすく、重要なのは計算の実施であり、私は
trueオブジェクトを実施して問題を解決した.アルゴリズムの問題を解くとき、高速コードではなく、可読性の良いコードを書く傾向があります.コードの長さは他の人より長いことが多い.スピードも速くない.しかし、実際の仕事で役に立つと思います.
public class BJ9019 {
// ...
static class State {
final int number;
final char beforeCommand;
final int beforeNumber;
final int[] digit;
public State(int number) {
this.number = number;
this.beforeCommand = COMMAND_START;
this.beforeNumber = -1;
this.digit = getDigit(number);
}
public State(int number, char beforeCommand, int beforeNumber, int[] digit) {
this.number = number;
this.beforeCommand = beforeCommand;
this.beforeNumber = beforeNumber;
this.digit = digit;
}
public State D() {
final int nextNumber = (2 * number) % 10_000;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_D, number, getDigit(nextNumber));
}
public State S() {
final int nextNumber = number == 0
? 9999
: number - 1;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_S, number, getDigit(nextNumber));
}
public State L() {
final int[] nextDigit = {
digit[1], digit[2], digit[3], digit[0],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_L, number, nextDigit);
}
public State R() {
final int[] nextDigit = {
digit[3], digit[0], digit[1], digit[2],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_R, number, nextDigit);
}
private static int[] getDigit(int num) {
final int[] nextDigit = new int[4];
for (int i = 3; i >= 0; i--) {
nextDigit[i] = num % 10;
num /= 10;
}
return nextDigit;
}
private static int getNumber(int[] digit) {
int number = 0;
for (int num: digit) {
number *= 10;
number += num;
}
return number;
}
}falseオブジェクトの作業は非常に簡単です.現在の状態でDSLRコマンドを実行すると、次のStateオブジェクトが返されます.4桁の数字は、コマンド用の
StateとStateで構成されています.次に、L配列を、R配列のint[4]値と相互に変換する方法が定義される.int[4]は、ステータスがどのコマンドによって到着したかに関する情報を含み、後でコマンドの順序を復元する.このようにして
intオブジェクトが実装された後、残りは典型的なBFSコードにすぎない.正解
package bj.comito.codeplus.practice;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class BJ9019 {
private static final Deque<State> q = new LinkedList<>();
private static final Deque<Character> q2 = new LinkedList<>();
private static final State[] visited = new State[10_000];
private static final char COMMAND_START = '0';
private static final char COMMAND_D = 'D';
private static final char COMMAND_S = 'S';
private static final char COMMAND_L = 'L';
private static final char COMMAND_R = 'R';
public static void main(String[] args) throws Throwable {
final BufferedReader br = new BufferedReader(
new InputStreamReader(System.in), 1<<10
);
final BufferedWriter bw = new BufferedWriter(
new OutputStreamWriter(System.out), 1<<10
);
final int T = Integer.parseInt(br.readLine());
for (int ti = 0; ti < T; ti++) {
final StringTokenizer st = new StringTokenizer(br.readLine(), " ");
final int start = Integer.parseInt(st.nextToken());
final int end = Integer.parseInt(st.nextToken());
bw.write(solve(start, end));
bw.write('\n');
}
bw.flush();
bw.close();
br.close();
}
private static String solve(int start, int end) {
q.clear();
Arrays.fill(visited, null);
State s = new State(start);
q.offer(s);
visited[start] = s;
while (!q.isEmpty()) {
State cur = q.poll();
if (cur.number == end) {
break;
}
State next;
next = cur.D();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.S();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.L();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
next = cur.R();
if (next != null) {
q.offer(next);
visited[next.number] = next;
}
}
return printCommands(end);
}
private static String printCommands(int end) {
State state = visited[end];
while (state.beforeCommand != COMMAND_START) {
q2.push(state.beforeCommand);
state = visited[state.beforeNumber];
}
StringBuilder sb = new StringBuilder(1<<8 + 1);
while (!q2.isEmpty()) {
sb.append(q2.pop());
}
return sb.toString();
}
static class State {
final int number;
final char beforeCommand;
final int beforeNumber;
final int[] digit;
public State(int number) {
this.number = number;
this.beforeCommand = COMMAND_START;
this.beforeNumber = -1;
this.digit = getDigit(number);
}
public State(int number, char beforeCommand, int beforeNumber, int[] digit) {
this.number = number;
this.beforeCommand = beforeCommand;
this.beforeNumber = beforeNumber;
this.digit = digit;
}
public State D() {
final int nextNumber = (2 * number) % 10_000;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_D, number, getDigit(nextNumber));
}
public State S() {
final int nextNumber = number == 0
? 9999
: number - 1;
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_S, number, getDigit(nextNumber));
}
public State L() {
final int[] nextDigit = {
digit[1], digit[2], digit[3], digit[0],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_L, number, nextDigit);
}
public State R() {
final int[] nextDigit = {
digit[3], digit[0], digit[1], digit[2],
};
final int nextNumber = getNumber(nextDigit);
if (visited[nextNumber] != null) {
return null;
}
return new State(nextNumber, COMMAND_R, number, nextDigit);
}
private static int[] getDigit(int num) {
final int[] nextDigit = new int[4];
for (int i = 3; i >= 0; i--) {
nextDigit[i] = num % 10;
num /= 10;
}
return nextDigit;
}
private static int getNumber(int[] digit) {
int number = 0;
for (int num: digit) {
number *= 10;
number += num;
}
return number;
}
}
}Reference
この問題について([白駿9019]DSLR), 我々は、より多くの情報をここで見つけました https://velog.io/@undefcat/백준-9019-DSLRテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol