BOJ 1937:欲張りパンダ

問題を解く

パンダの解放の起点から、パンダが移動して生存できる最も長い時間の問題を探しています.
私の考えは以下の通りです.

パンダを放出する位置はまだ確定していないため、for文ですべての位置からパンダを放出する数を求めることができる.

の最長生存時間を得る必要があるので、この場所に最長の移動時間を貯蔵して使用することができる.

どんな順番で作った問題か見てみましょう.

本の木が保存されている地図を使って、パンダが生存できる最長日数を保存します.

2ではfor文で地図をすべて巡回する.

現在位置curi、curjの中ですでに獲得した最長の場合は、あなたに返却されます.

curIを求めて、curJの中で移動可能なnextI、nextJ.

nextI、nextJの竹が現在のcuri、curJの竹より多い場合は移動可能であり、現在のアクセスに格納されている数に比べて最大値を入れる.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 1;
        int[][] visit = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                answer = Math.max(answer, solution(visit, i, j));
            }
        }

        System.out.println(answer);
    }

    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    static int solution(int[][] visit, int curI, int curJ) {
        if(visit[curI][curJ] != 0) {
            return visit[curI][curJ];
        }

        visit[curI][curJ] = 1;
        for(int index = 0; index < 4; index++) {
            int nextI = curI + dirI[index];
            int nextJ = curJ + dirJ[index];

            if(nextI >= N || nextI < 0 || nextJ >= N || nextJ < 0) {
                continue;
            }
            if(map[curI][curJ] < map[nextI][nextJ]) {
                visit[curI][curJ] = Math.max(visit[curI][curJ], solution(visit, nextI, nextJ) + 1);
            }
        }

        return visit[curI][curJ];
    }
}

github
白駿