BOJ1600. 말이 되고픈 원숭이
✔문제링크
BOJ1600. 말이 되고픈 원숭이
📝문제설명
💡해결방법
👍코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int K, W, H, ANS;
static int map[][];
static int dis[][][];
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int hdx[] = {-2,-1,1,2,2,1,-1,-2};
static int hdy[] = {1,2,2,1,-1,-2,-2,-1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
K = sc.nextInt();
W = sc.nextInt();
H = sc.nextInt();
map = new int[H][W];
dis = new int[H][W][K+1];
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
map[i][j] = sc.nextInt();
}
}
ANS = -1;
Queue<Move> q = new LinkedList<>();
q.add(new Move(0, 0, 0, 0));
dis[0][0][0] = 1;
while(!q.isEmpty()) {
Move mo = q.poll();
int x = mo.x;
int y = mo.y;
if(x == H-1 && y== W-1) {
ANS = mo.cnt;
break;
}
for(int k=0; k<4; k++) {
int xx = x+dx[k];
int yy = y+dy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h]!=0) continue;
dis[xx][yy][mo.h] = 1;
q.add(new Move(xx, yy, mo.h, mo.cnt+1));
}
if(mo.h <= K-1) {
for(int k=0; k<8; k++) {
int xx = x+hdx[k];
int yy = y+hdy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h+1]!=0) continue;
dis[xx][yy][mo.h+1] = 1;
q.add(new Move(xx, yy, mo.h+1, mo.cnt+1));
}
}
}
System.out.println(ANS);
}
public static class Move {
int x, y, h, cnt;
public Move(int x, int y, int h, int cnt) {
this.x = x;
this.y = y;
this.h = h;
this.cnt = cnt;
}
}
}
Author And Source
이 문제에 관하여(BOJ1600. 말이 되고픈 원숭이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gisung/BOJ1600.-말이-되고픈-원숭이
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
💡해결방법
👍코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int K, W, H, ANS;
static int map[][];
static int dis[][][];
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int hdx[] = {-2,-1,1,2,2,1,-1,-2};
static int hdy[] = {1,2,2,1,-1,-2,-2,-1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
K = sc.nextInt();
W = sc.nextInt();
H = sc.nextInt();
map = new int[H][W];
dis = new int[H][W][K+1];
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
map[i][j] = sc.nextInt();
}
}
ANS = -1;
Queue<Move> q = new LinkedList<>();
q.add(new Move(0, 0, 0, 0));
dis[0][0][0] = 1;
while(!q.isEmpty()) {
Move mo = q.poll();
int x = mo.x;
int y = mo.y;
if(x == H-1 && y== W-1) {
ANS = mo.cnt;
break;
}
for(int k=0; k<4; k++) {
int xx = x+dx[k];
int yy = y+dy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h]!=0) continue;
dis[xx][yy][mo.h] = 1;
q.add(new Move(xx, yy, mo.h, mo.cnt+1));
}
if(mo.h <= K-1) {
for(int k=0; k<8; k++) {
int xx = x+hdx[k];
int yy = y+hdy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h+1]!=0) continue;
dis[xx][yy][mo.h+1] = 1;
q.add(new Move(xx, yy, mo.h+1, mo.cnt+1));
}
}
}
System.out.println(ANS);
}
public static class Move {
int x, y, h, cnt;
public Move(int x, int y, int h, int cnt) {
this.x = x;
this.y = y;
this.h = h;
this.cnt = cnt;
}
}
}
Author And Source
이 문제에 관하여(BOJ1600. 말이 되고픈 원숭이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@gisung/BOJ1600.-말이-되고픈-원숭이
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int K, W, H, ANS;
static int map[][];
static int dis[][][];
static int dx[] = {-1,1,0,0};
static int dy[] = {0,0,-1,1};
static int hdx[] = {-2,-1,1,2,2,1,-1,-2};
static int hdy[] = {1,2,2,1,-1,-2,-2,-1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
K = sc.nextInt();
W = sc.nextInt();
H = sc.nextInt();
map = new int[H][W];
dis = new int[H][W][K+1];
for(int i=0; i<H; i++) {
for(int j=0; j<W; j++) {
map[i][j] = sc.nextInt();
}
}
ANS = -1;
Queue<Move> q = new LinkedList<>();
q.add(new Move(0, 0, 0, 0));
dis[0][0][0] = 1;
while(!q.isEmpty()) {
Move mo = q.poll();
int x = mo.x;
int y = mo.y;
if(x == H-1 && y== W-1) {
ANS = mo.cnt;
break;
}
for(int k=0; k<4; k++) {
int xx = x+dx[k];
int yy = y+dy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h]!=0) continue;
dis[xx][yy][mo.h] = 1;
q.add(new Move(xx, yy, mo.h, mo.cnt+1));
}
if(mo.h <= K-1) {
for(int k=0; k<8; k++) {
int xx = x+hdx[k];
int yy = y+hdy[k];
if(xx<0 || xx>=H || yy<0 || yy>=W || map[xx][yy]!=0) continue;
if(dis[xx][yy][mo.h+1]!=0) continue;
dis[xx][yy][mo.h+1] = 1;
q.add(new Move(xx, yy, mo.h+1, mo.cnt+1));
}
}
}
System.out.println(ANS);
}
public static class Move {
int x, y, h, cnt;
public Move(int x, int y, int h, int cnt) {
this.x = x;
this.y = y;
this.h = h;
this.cnt = cnt;
}
}
}
Author And Source
이 문제에 관하여(BOJ1600. 말이 되고픈 원숭이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gisung/BOJ1600.-말이-되고픈-원숭이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)