题解

题面描述

给定一个大小为 $k\times k$ 的二维矩阵 map[][]，表示二维空间中的一个地图，其中 map[i][j] 表示位置 $(i,j)$ 上的地形高度。玩家控制一个角色从矩阵左上角位置 $(0,0)$ 进入，从矩阵右侧任意位置出去。

1. 角色在矩阵中只能向右或向下移动；
2. 如果相邻两个节点高度差大于 $1$，则角色不能移动过去；
3. 角色通过 $(i,j)$ 地点时，会消耗 $map[i][j]$ 的体力值。

要求计算最省体力值的路线所消耗的体力值。

• 若不存在可行路径，返回 $-1$；
• 若参数不合法（包括 $k\le0$ 或 $k>100$，或任意 $map[i][j]$ 不在 $[0,10]$ 范围内），返回 $-2$。

思路

1. 参数校验
   • 判断 $k$ 是否在 $1\le k\le100$；
   • 判断所有 $map[i][j]$ 是否满足 $0\le map[i][j]\le10$；
   • 任一不满足则直接输出 $-2$。
2. 状态定义
   • 用 $dp[i][j]$ 表示从起点 $(0,0)$ 到达位置 $(i,j)$ 的最小体力消耗。
3. 初始化
   • 所有 $dp[i][j]$ 设为一个极大值 $\infty$；
   • $dp[0][0]=map[0][0]$。
4. 状态转移
   • 对于每个格子 $(i,j)$，考虑从上方或左方转移，前提是高度差不超过 $1$：
     |$map[i][j]$-$map[i-1][j]$|<=$1$,|$map[i][j]$-$map[i][j-1]$<=$1$
   • 则
     $dp[i][j]$=min($dp[i-1][j]$,$dp[i][j-1]$)+$map[i][j]$
5. 结果计算
   • 最终答案为最右一列中最小的 $dp[i][k-1]$；
   • 若仍为 $\infty$，则无可行路径，输出 $-1$。

整体时间复杂度 $O(k^2)$，空间复杂度 $O(k^2)$，满足题目要求。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k;
    if (!(cin >> k)) return 0;
    // 参数 k 合法性检查
    if (k <= 0 || k > 100) {
        cout << -2;
        return 0;
    }
    vector<vector<int>> mp(k, vector<int>(k));
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            cin >> mp[i][j];
            // 地形高度合法性检查
            if (mp[i][j] < 0 || mp[i][j] > 10) {
                cout << -2;
                return 0;
            }
        }
    }
    const int INF = 1e9;
    vector<vector<int>> dp(k, vector<int>(k, INF));
    dp[0][0] = mp[0][0];  // 起点消耗

    // 动态规划填表
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (i > 0 && abs(mp[i][j] - mp[i-1][j]) <= 1) {
                dp[i][j] = min(dp[i][j], dp[i-1][j] + mp[i][j]);
            }
            if (j > 0 && abs(mp[i][j] - mp[i][j-1]) <= 1) {
                dp[i][j] = min(dp[i][j], dp[i][j-1] + mp[i][j]);
            }
        }
    }

    // 从最右列任意位置出去
    int ans = INF;
    for (int i = 0; i < k; i++) {
        ans = min(ans, dp[i][k-1]);
    }
    // 输出结果
    if (ans == INF) cout << -1;
    else cout << ans;
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    k = int(data[0])
    # 参数 k 合法性检查
    if k <= 0 or k > 100:
        print(-2)
        return

    mp = []
    idx = 1
    for _ in range(k):
        row = list(map(int, data[idx:idx+k]))
        # 地形高度合法性检查
        if any(v < 0 or v > 10 for v in row):
            print(-2)
            return
        mp.append(row)
        idx += k

    INF = 10**9
    dp = [[INF]*k for _ in range(k)]
    dp[0][0] = mp[0][0]  # 起点消耗

    for i in range(k):
        for j in range(k):
            if i > 0 and abs(mp[i][j] - mp[i-1][j]) <= 1:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + mp[i][j])
            if j > 0 and abs(mp[i][j] - mp[i][j-1]) <= 1:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + mp[i][j])

    ans = min(dp[i][k-1] for i in range(k))
    print(-1 if ans >= INF else ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());
        // 参数 k 合法性检查
        if (k <= 0 || k > 100) {
            System.out.println(-2);
            return;
        }

        int[][] mp = new int[k][k];
        for (int i = 0; i < k; i++) {
            String[] parts = br.readLine().split("\\s+");
            for (int j = 0; j < k; j++) {
                mp[i][j] = Integer.parseInt(parts[j]);
                // 地形高度合法性检查
                if (mp[i][j] < 0 || mp[i][j] > 10) {
                    System.out.println(-2);
                    return;
                }
            }
        }

        final int INF = 1_000_000_000;
        int[][] dp = new int[k][k];
        for (int i = 0; i < k; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][0] = mp[0][0];  // 起点消耗

        // 动态规划填表
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                if (i > 0 && Math.abs(mp[i][j] - mp[i-1][j]) <= 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + mp[i][j]);
                }
                if (j > 0 && Math.abs(mp[i][j] - mp[i][j-1]) <= 1) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + mp[i][j]);
                }
            }
        }

        // 从最右列任意位置出去
        int ans = INF;
        for (int i = 0; i < k; i++) {
            ans = Math.min(ans, dp[i][k-1]);
        }
        System.out.println(ans == INF ? -1 : ans);
    }
}

题目内容

小明用$k*k$的二维矩阵$map[][]$表示三维空间中的一个地图，$map[i][j]$表示位置$[i,j]$上的地形高度，玩家需控制游戏中的一个角色穿过这个地图，从矩阵左上角位置(坐标$0,0$)进入，从矩阵右侧任意位置出去。

1.角色在矩阵中只能向右或向下移动

2.如果相邻两个节点高度差大于$1$，则角色不能移动过去(太高角色爬不上去，太低了就摔死了)

3.角色通过$(i,j)$地点时，会消耗$map[i][j]$体力值。

求最省体力值的路线所消耗的体力值。

输入描述

输入有多行，第$1$行为数组的行数$k(k<=100)$，第$2$行至第$k+1$行为$k*k$矩阵，数组元素用空格分隔，$0<= map[i][j]<=10$ 例如: $3$ $1\ 2\ 3$ $5\ 5\ 5$ $7\ 7\ 7$

输出描述

输出一行，一个整数，表示最省体力值的路线所消耗的体力值。

当不存在可行路径，返回$-1$

参数不合法时返回$-2$

样例1

输入

3
1 2 3
5 5 5
7 7 7

输出

6

说明

通过路径的矩阵坐标为$[0,0],[0,1],[0,2]$，依次消耗了$1,2,3$体力值，共计$6$。其他路径由于高度差无法通过，因此最优解是$6$

样例2

输入

3
1 2 4
6 6 6
8 8 8

输出

-1

说明

由于高度差，没有可达到右侧的路径，返回-1

样例3

输入

3
1 2 1
1 1 2
9 9 9

输出

4

说明

红色路线消耗体力值为$4$，黄色路线消耗体力值为$5$，因此最优解为$4$。 (当然还存在其他路线，但都不如红色路线体力值小，本示例主要解释路径最优)