https://www.acmicpc.net/problem/7562
나이트가 이동할 수 있는 범위를 내에서 하나씩 탐색하면서 출발 좌표에서 도착 좌표까지 이동하는데 거치는 최소 칸 수를 구하는 문제이다.
다음 좌표에 이전 좌표값 +1을 해서 구해주면 된다.
package graph.b7562;
import javafx.scene.chart.BubbleChart;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class b7562 {
static int i;
static int[][] map;
static boolean[][] check;
static int[] dx = {-2, -2, -1, 1, 2, 2, 1, -1};
static int[] dy = {-1, 1, 2, 2, 1, -1, -2, -2};
static Queue<Point> queue;
// 출빌 좌표
static int startX;
static int startY;
// 도착 좌표
static int endX;
static int endY;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
i = Integer.parseInt(br.readLine());
map = new int[i][i];
check = new boolean[i][i];
StringTokenizer st = new StringTokenizer(br.readLine());
startX = Integer.parseInt(st.nextToken());
startY = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
endX = Integer.parseInt(st.nextToken());
endY = Integer.parseInt(st.nextToken());
bfs(startX, startY, endX, endY);
System.out.println(map[endX][endY]);
}
}
public static void bfs(int a, int b, int c, int d) {
queue = new LinkedList<>();
queue.add(new Point(a, b));
check[a][b] = true;
while (!queue.isEmpty()) {
Point point = queue.poll();
// 이동하면서 탐색
for (int k = 0; k < 8; k++) {
int nx = point.x + dx[k];
int ny = point.y + dy[k];
if (nx >= 0 && ny >= 0 && nx < i && ny < i) {
if (!check[nx][ny]) {
queue.add(new Point(nx, ny));
check[nx][ny] = true;
map[nx][ny] = map[point.x][point.y] + 1;
}
}
}
}
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}