白駿-1600号は馬の猿になりたい

方法

ソース

import java.io.*;
import java.util.*;

public class Main {
	static int K;
	static int W, H;
	static int[][] Board;
	static int[][] Dir = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
							{2, 1}, {1, 2}, {-1, 2}, {-2, 1},
							{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	static boolean[][][] Visit;
	static int Answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		K = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		Board = new int[H][W];
		Visit = new boolean[H][W][K+1]; // x, y 좌표로 이동하는데 k 말처럼 이동하여 방문하였는지 체크
		for(int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < W; j++) {
				Board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		bfs();
		if(Answer == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(Answer);
	}
	static void bfs() {
		Queue<Point_b1600> q = new LinkedList<Point_b1600>();
		q.offer(new Point_b1600(0, 0, 0, 0));
		Visit[0][0][0] = true; //0, 0은 말처럼 0번 움직여서 방문한거
		
		while(!q.isEmpty()) {
			Point_b1600 cur = q.poll();
			int cx = cur.x;
			int cy = cur.y;
			int cMcnt = cur.moveCnt;
			int cNcnt = cur.nightCnt;
			
			if(cx == H-1 && cy == W-1) {
				Answer = cMcnt < Answer ? cMcnt : Answer; 
			}
			
			int loopCnt = cNcnt < K ? 0 : 8;
			
			for(int i = loopCnt; i < Dir.length; i++) {
				int nx = cx + Dir[i][0];
				int ny = cy + Dir[i][1];
				
				//범위밖이면 바로 패스
				if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
				
				//범위 내인데, X면 못감.
				if(Board[nx][ny] == 1) continue;
				
				boolean isNightMove = i < 8 ? true : false; //0~7이면 말처럼 이동이고, 8~11이면 일반 이동
				
				// 해당 좌표에 말처럼 움직이는데, 방문한적이 없으면 방문
				if(isNightMove && !Visit[nx][ny][cNcnt+1]) {
					//방문처리해주고, q에 offer
					Visit[nx][ny][cNcnt+1] = true;
					q.offer(new Point_b1600(nx, ny, cMcnt+1, cNcnt+1));
				} 
				// 해당 좌표에 말처럼 움직이지 않았는데, 방문한적이 없으면 방문
				else if(!isNightMove && !Visit[nx][ny][cNcnt]) {
					Visit[nx][ny][cNcnt] = true;
					q.offer(new Point_b1600(nx, ny, cMcnt+1, cNcnt));
				}
			}
		}		
	}
}

class Point_b1600{
	int x;
	int y;
	int moveCnt;
	int nightCnt;
	Point_b1600(int x, int y, int moveCnt, int nightCnt){
		this.x = x;
		this.y = y;
		this.moveCnt = moveCnt;
		this.nightCnt = nightCnt;
	}
}