地形の移動

アルゴリズムの資料は私も自分で解答したことがありますが、他の人との解答の比較を通じて、私が整理したこれらの資料はもっと良いアルゴリズムを学ぶためです.

プログラマ-地形移動

https://programmers.co.kr/learn/courses/30/lessons/62050
解答:最低点x,yを検索し,DFSアルゴリズムにより,hより高い層のすべての場所にアクセスする.h以上の箇所はPriorityQueueに入り、DFSアルゴリズムでコストを加算し、DFSアルゴリズムでアクセスの有無を確認します.

import java.util.*;
class Solution {
    static int [][] arr;
    static boolean [][] chk;
    static int cost = 0, cnt = 0;
    static PriorityQueue <int []> pq = new PriorityQueue<int []>((a,b) -> Math.abs(a[2]-a[3])-Math.abs(b[2]-b[3]));
    public int solution(int[][] land, int height) {
        int n = land.length,  x = 0, y = 0, min = Integer.MAX_VALUE;;
	arr = new int [n+2][n+2];
	chk = new boolean [n+2][n+2]; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if(land[i][j] < min) {
				min = land[i][j];
				y = i+1;
				x = j+1;
			}
			arr[1+i][1+j] = land[i][j];
		}
	}
	while(cnt < n*n) {
		visit(x,y, height);
		while(!pq.isEmpty()) {
			int [] data = pq.poll();
			if(!chk[data[1]][data[0]]) {
				x = data[0];
				y = data[1];
				cost += Math.abs(data[2] - data[3]);
				break;
			}
		}
	}
       return cost;
    }
    private static void visit(int a, int b, int h) {
	while(!pq.isEmpty()) {
		if(chk[pq.peek()[1]][pq.peek()[0]]) pq.poll();
		else break;
	}
	cnt++;
	chk[b][a] = true;
	int [] dx = {0, 0, 1, -1};
	int [] dy = {1, -1, 0, 0};
	for (int i = 0; i < 4; i++) {
		int nx = a + dx[i];
		int ny = b + dy[i];
		if(arr[ny][nx] != 0 && !chk[ny][nx]) {
			if(Math.abs(arr[ny][nx] - arr[b][a]) <= h) {
				visit(nx, ny, h);
			}
			else {
				pq.add(new int [] {nx, ny, arr[ny][nx], arr[b][a] });
			}
		}
	}
}
}