白駿16928号)蛇と梯子遊び(再開)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static HashMap<Integer, Integer> map = new HashMap<>();
static class Location {
int n, distance;
public Location(int n, int distance) {
this.n = n;
this.distance = distance;
}
}
public static int BFS(int start_point, int last_point) {
boolean[] visited = new boolean[101];
Queue<Location> will_visit = new LinkedList<Location>();
Location start = new Location(start_point, 0);
will_visit.add(start);
while (will_visit.size() > 0) {
Location current_point = will_visit.remove();
if (current_point.n == last_point)
return current_point.distance;
if (current_point.n < 1 || current_point.n > 100)
continue;
if (visited[current_point.n])
continue;
visited[current_point.n] = true;
if(map.containsKey(current_point.n))
{
will_visit.add(new Location(map.get(current_point.n), current_point.distance));
}
else
{
will_visit.add(new Location(current_point.n + 1, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 2, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 3, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 4, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 5, current_point.distance + 1));
will_visit.add(new Location(current_point.n + 6, current_point.distance + 1));
}
}
return -1;
}
static void start_game()
{
System.out.println(BFS(1,100));
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
for(int i=0;i<N;i++) {
String [] XY = reader.readLine().split(" ");
int x = Integer.parseInt(XY[0]);
int y = Integer.parseInt(XY[1]);
map.put(x, y);
}
for(int i=0 ; i<M ; i++) {
String [] UV = reader.readLine().split(" ");
int u = Integer.parseInt(UV[0]);
int v = Integer.parseInt(UV[1]);
map.put(u, v);
}
start_game();
reader.close();
}
}
--------修正----------import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static HashMap<Integer, Integer> map = new HashMap<>();
static int[] board = new int[101];
static class Location {
int n, distance;
public Location(int n, int distance) {
this.n = n;
this.distance = distance;
}
}
public static int BFS(int start_point, int last_point) {
boolean[] visited = new boolean[101];
Queue<Location> will_visit = new LinkedList<Location>();
Location start = new Location(start_point, 0);
will_visit.add(start);
while (will_visit.size() > 0) {
Location current_point = will_visit.poll();
visited[current_point.n] = true;
if (current_point.n == last_point)
return current_point.distance;
for (int i = 1; i <= 6; i++) {
int nnow = current_point.n+i;
if (100 < nnow)
continue;
if (visited[nnow])
continue;
visited[nnow] = true;
Location next_point = new Location(nnow, current_point.distance + 1);
if (map.containsKey(next_point.n)) {
int ntemp = map.get(next_point.n);
if (!visited[ntemp]) {
visited[ntemp] = true;
will_visit.add(new Location(ntemp, current_point.distance + 1));
}
} else {
will_visit.add(next_point);
}
}
}
return -1;
}
static void start_game() {
System.out.println(BFS(1, 100));
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int M = Integer.parseInt(stringTokenizer.nextToken());
for (int i = 0; i < N; i++) {
String[] XY = reader.readLine().split(" ");
int x = Integer.parseInt(XY[0]);
int y = Integer.parseInt(XY[1]);
map.put(x, y);
}
for (int i = 0; i < M; i++) {
String[] UV = reader.readLine().split(" ");
int u = Integer.parseInt(UV[0]);
int v = Integer.parseInt(UV[1]);
map.put(u, v);
}
start_game();
reader.close();
}
}
Reference
この問題について(白駿16928号)蛇と梯子遊び(再開)), 我々は、より多くの情報をここで見つけました https://velog.io/@yuiopre98/백준-16928번-뱀과-사다리-게임-다시풀어보기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol