package math;
import java.io.*;
import java.util.*;
public class Sep4Week_1004_Kse {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int testCase = 0;
static int[][] board = new int[2001][2001];
static int[] start = new int[2];
static int[] end = new int[2];
static int N;
static int circleIndex;
static int[] dy = new int[] {1, 0, -1, 1, -1, 1, 0, -1};
static int[] dx = new int[] {-1,-1,-1, 0, 0, 1, 1, 1};
static ArrayList<int[]> circleList = new ArrayList<>();
public static void main(String[] args) throws IOException {
testCase = Integer.parseInt(br.readLine());
for (int t = 0; t < testCase; t++) {
for (int i = 0; i <= 2000; i++) {
Arrays.fill(board[i], 0);
}
circleIndex = 1;
circleList.clear();
st = new StringTokenizer(br.readLine());
start[0] = convertCoordinate(st.nextToken());
start[1] = convertCoordinate(st.nextToken());
end[0] = convertCoordinate(st.nextToken());
end[1] = convertCoordinate(st.nextToken());
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int c1 = convertCoordinate(st.nextToken());
int c2 = convertCoordinate(st.nextToken());
int r = Integer.parseInt(st.nextToken());
circleList.add(new int[] {c1, c2, r});
}
circleList.sort((a, b) -> b[2] - a[2]);
for (int[] circle : circleList) {
makeCircleArea(circle[0], circle[1], circle[2]);
}
/* board[start[0]][start[1]] = -1;
board[end[0]][end[1]] = -2;
for (int i =994; i < 1015; i++) {
for (int j = 994; j < 1015; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}*/
System.out.println(solve());
}
}
static int solve () {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
int[][] D = new int[2001][2001];
for (int i = 0; i < 2001; i++) {
Arrays.fill(D[i], 987654321);
}
D[start[0]][start[1]] = 0;
pq.add(new int[] {start[0], start[1], 0});
while(!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[0] == end[0] && cur[1] == end[1]) {
return cur[2];
}
int curCirecleIndex = board[cur[0]][cur[1]];
for (int k = 0; k < 8; k++) {
int nx = dx[k] + cur[0];
int ny = dy[k] + cur[1];
if (nx >= 0 && nx < 2001 && ny >= 0 && ny < 2001) {
int cost = cur[2];
if (curCirecleIndex != board[nx][ny]) {
cost += 1;
if (curCirecleIndex != 0 && board[nx][ny] != 0) {
cost += 1;
}
}
if (cost < D[nx][ny]) {
pq.add(new int[] {nx, ny, cost});
D[nx][ny] = cost;
}
}
}
}
return 0;
}
static void makeCircleArea (int c1, int c2, int r) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {c1, c2});
boolean[][] visited = new boolean[2001][2001];
int rSquare = r * r;
int cycle = r + 1;
while (!q.isEmpty() && cycle > 0) {
int qSize = q.size();
for (int i = 0; i < qSize; i++) {
int[] cur = q.poll();
for (int k = 0; k < 8; k++){
int nx = dx[k] + cur[0];
int ny = dy[k] + cur[1];
if (nx >= 0 && nx < 2001 && ny >= 0 && ny < 2001) {
if (visited[nx][ny]) continue;
int dist = (nx - c1) * (nx - c1) + (ny - c2) * (ny - c2);
if (dist <= rSquare) {
board[nx][ny] = circleIndex;
q.add(new int[] {nx, ny});
visited[nx][ny] = true;
}
}
}
}
cycle--;
}
circleIndex++;
}
static int convertCoordinate (String n) {
return Integer.parseInt(n) + 1000;
}
}
Bash
복사