小猿的迷宫之旅

有一个N*M大小的迷宫矩阵，迷宫的每一个格子有一个数值（a[i][j] <10^9）。小猿在迷宫中发现，它只能朝着上下左右四个方向的相邻格子前进，并且只能进入比当前位置数值更大的格子。但是小猿有个紧急呼救按钮，他可以通过按下按钮，强行进入到不满足数值大小要求的相邻格子，可惜这个按钮只能按K次。请问小猿从这个迷宫任选一个格子出发，在紧急呼救按钮的帮助下，最多能走多少步（开始位置计入步数，即站在起点是步数为1）。
解法：深度优先遍历+动态规划
时间复杂度,只能通过80%

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner input;
        int N, M, K, i, j;
        int[][] grid;

        input = new Scanner(System.in);
        while(input.hasNext()){
            N = input.nextInt();
            M = input.nextInt();
            K = input.nextInt();
            grid = new int[N][M];
            for(i = 0; i < N; i++){
                for(j = 0; j < M; j++){
                    grid[i][j] = input.nextInt();
                }
            }
            System.out.println(new Main().Solution(grid, N, M, K + 1));
        }
    }

    private int Solution(int[][] grid, int N, int M, int K){
        int[][][] dp;
        int i, j, k, ans;

        dp = new int[N][M][K+1];

        for(k = 1; k <= K; k++){
            for(i = 0; i < N; i++){
                for(j = 0; j < M; j++){
                    if(dp[i][j][k] == 0)
                        dfs(dp, i, j, k, grid, N, M, grid[i][j] - 1);
                }
            }
        }
        ans = 0;
        for(i = 0; i < N; i++){
            for(j = 0; j < M; j++){
                ans = ans > dp[i][j][K] ? ans : dp[i][j][K];
            }
        }
        return ans;
    }

    private int dfs(int[][][] dp, int i, int j, int k, int[][] grid, int N, int M, int s){
        int ans, next;

        if(i < 0 || i == N || j < 0 || j == M)
            return 0;
        if(grid[i][j] <= s)
            return dp[i][j][k-1];
        if(dp[i][j][k] != 0)
            return dp[i][j][k];
        ans = 0;
        next = dfs(dp, i + 1, j, k, grid, N, M, grid[i][j]);
        ans = ans > next ? ans : next;
        next = dfs(dp, i - 1, j, k, grid, N, M, grid[i][j]);
        ans = ans > next ? ans : next;
        next = dfs(dp, i, j + 1, k, grid, N, M, grid[i][j]);
        ans = ans > next ? ans : next;
        next = dfs(dp, i, j - 1, k, grid, N, M, grid[i][j]);
        ans = ans > next ? ans : next;
        dp[i][j][k] = ++ans;
        return dp[i][j][k];
    }
}

迭代

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner input;
        int N, M, K, i, j;
        int[][] grid;

        input = new Scanner(System.in);
        while(input.hasNext()){
            N = input.nextInt();
            M = input.nextInt();
            K = input.nextInt();
            grid = new int[N][M];
            for(i = 0; i < N; i++){
                for(j = 0; j < M; j++){
                    grid[i][j] = input.nextInt();
                }
            }
            System.out.println(new Main().Solution(grid, K + 1, N, M));
        }
    }

    private int Solution(int[][] grid, int K, int N, int M){
        int[][][] dp;
        int[][] deltas;
        int[] cursor;
        int i, j, k, n, m, max, ans;
        Stack<int[]> stack;

        dp = new int[N][M][K+1];
        stack = new Stack<>();
        deltas = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        cursor = null;
        for(k = 1; k <= K; k++){
            for(i = 0; i < N; i++){
                for(j = 0; j < M; j++){
                    if(dp[i][j][k] != 0)
                        continue;
                    stack.push(new int[]{i, j});
                    while(!stack.isEmpty()){
                        while(cursor != stack.peek()){
                            cursor = stack.peek();
                            for(int[] delta : deltas){
                                n = cursor[0] + delta[0];
                                m = cursor[1] + delta[1];
                                if(n < 0 || n == N || m < 0 || m == M)
                                    continue;
                                if(grid[n][m] > grid[cursor[0]][cursor[1]] && dp[n][m][k] == 0){
                                    stack.push(new int[]{n, m});
                                }
                            }
                        }
                        cursor = stack.pop();
                        max = 0;
                        for(int[] delta : deltas){
                            n = cursor[0] + delta[0];
                            m = cursor[1] + delta[1];
                            if(n < 0 || n == N || m < 0 || m == M)
                                continue;
                            max = Math.max(max, grid[n][m] > grid[cursor[0]][cursor[1]] ? dp[n][m][k] : dp[n][m][k-1]);
                        }
                        dp[cursor[0]][cursor[1]][k] = max + 1;
                    }
                }
            }
        }
        ans = 0;
        for(i = 0; i < N; i++){
            for(j = 0; j < M; j++){
                ans = Math.max(ans, dp[i][j][K]);
            }
        }
        return ans;
    }
}