[伯俊]1600号馬になりたい猿JAVA草
25862 ワード
問題のショートカット
私の答え
私の答え
最初の解ではdepthとreseをそれぞれの静的変数として宣言し、bfsメソッド内で分岐して追加、減算、確認します.
ただ、そのプールのメモリが超過しています.
最終的にこの問題の要旨は,アクセス中に前後に1格移動するアクセスは継続できるが,以前の「馬」移動経路の1つの位置に1格移動するパスが到着するとアクセスは継続できない.
このためには、アクセスの配置を3 Dのvisited[x][y][remain]
として宣言する必要があります.import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 하나의 이동경로에 의한 좌표 x,y와 이동 횟수 depth, 남은 '말' 이동횟수 remain
class Point {
public int x;
public int y;
public int depth;
public int remain;
public Point(int x, int y, int depth, int remain) {
this.x = x;
this.y = y;
this.depth = depth;
this.remain = remain;
}
}
class Main {
static int k, row, col;
//이 문제에서 가장 중요한 부분
//단순히 그 좌표지점에 방문했었는지가 중요한게 아니라 그 방문지점에 remain이 같게 도착했느냐가 관건이다
static boolean[][][] visited;
static int[][] map;
static Queue<Point> q;
static int[] dx = {1,0,-1,0,2,2,1,1,-1,-1,-2,-2};
static int[] dy = {0,-1,0,1,1,-1,2,-2,2,-2,1,-1};
public static void main(String[] args) throws IOException {
//input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
visited = new boolean[row][col][31];
map = new int[row][col];
q = new LinkedList<>();
for (int i = 0; i < row; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st2.nextToken());
}
}
//logic
q.offer(new Point(0,0, 0, k));
int result = bfs();
//output
System.out.println(result);
}
public static int bfs() {
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Point po = q.poll();
int x = po.x;
int y = po.y;
int depth = po.depth;
int remain = po.remain;
// 범위 벗어난 경우
if (x < 0 || y < 0 || x >= row || y >= col) {
continue;
}
// 장애물 만난 경우
if (map[x][y] == 1) {
continue;
}
// 오른쪽 하단에 도착한 경우 depth 반환
if (x == row-1 && y == col-1) {
return depth;
}
// 이 지점에 들린게 문제가 아니라, 같은 remain을 가지고 들렸는지 체크
if (visited[x][y][remain]) {
continue;
}
// 방문 기록
visited[x][y][remain] = true;
// 한칸씩 움직이는 경우이므로 depth만 더해짐
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain));
}
// '말' 이동 횟수가 0이면 continue
if (remain == 0) continue;
// '말' 이동 횟수가 남았으면 이동시키고 depth는 +1, remain은 -1
for (int j = 4; j < 12; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain - 1));
}
}
}
return -1;
}
}
Reference
この問題について([伯俊]1600号馬になりたい猿JAVA草), 我々は、より多くの情報をここで見つけました
https://velog.io/@hahahaa8642/백준-1600번-말이-되고픈-원숭이-JAVA-풀이
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
// 하나의 이동경로에 의한 좌표 x,y와 이동 횟수 depth, 남은 '말' 이동횟수 remain
class Point {
public int x;
public int y;
public int depth;
public int remain;
public Point(int x, int y, int depth, int remain) {
this.x = x;
this.y = y;
this.depth = depth;
this.remain = remain;
}
}
class Main {
static int k, row, col;
//이 문제에서 가장 중요한 부분
//단순히 그 좌표지점에 방문했었는지가 중요한게 아니라 그 방문지점에 remain이 같게 도착했느냐가 관건이다
static boolean[][][] visited;
static int[][] map;
static Queue<Point> q;
static int[] dx = {1,0,-1,0,2,2,1,1,-1,-1,-2,-2};
static int[] dy = {0,-1,0,1,1,-1,2,-2,2,-2,1,-1};
public static void main(String[] args) throws IOException {
//input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
visited = new boolean[row][col][31];
map = new int[row][col];
q = new LinkedList<>();
for (int i = 0; i < row; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st2.nextToken());
}
}
//logic
q.offer(new Point(0,0, 0, k));
int result = bfs();
//output
System.out.println(result);
}
public static int bfs() {
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Point po = q.poll();
int x = po.x;
int y = po.y;
int depth = po.depth;
int remain = po.remain;
// 범위 벗어난 경우
if (x < 0 || y < 0 || x >= row || y >= col) {
continue;
}
// 장애물 만난 경우
if (map[x][y] == 1) {
continue;
}
// 오른쪽 하단에 도착한 경우 depth 반환
if (x == row-1 && y == col-1) {
return depth;
}
// 이 지점에 들린게 문제가 아니라, 같은 remain을 가지고 들렸는지 체크
if (visited[x][y][remain]) {
continue;
}
// 방문 기록
visited[x][y][remain] = true;
// 한칸씩 움직이는 경우이므로 depth만 더해짐
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain));
}
// '말' 이동 횟수가 0이면 continue
if (remain == 0) continue;
// '말' 이동 횟수가 남았으면 이동시키고 depth는 +1, remain은 -1
for (int j = 4; j < 12; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
q.offer(new Point(nx, ny, depth + 1, remain - 1));
}
}
}
return -1;
}
}
Reference
この問題について([伯俊]1600号馬になりたい猿JAVA草), 我々は、より多くの情報をここで見つけました https://velog.io/@hahahaa8642/백준-1600번-말이-되고픈-원숭이-JAVA-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol