✔문제링크

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;
		}
	}
}