蓝桥试题：混境之地（记忆化搜索）

游戏开发
2025-09-12 01:24:02

一、问题描述

小蓝有一天误入了一个混境之地。

好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息：

混境之地是一个n⋅m 大小的矩阵，其中第 i 行第 j 列的的点 h i j 表示第 i 行第 j 列的高度。他现在所在位置的坐标为 (A,B) ，而这个混境之地出口的坐标为 (C,D) ，当站在出口时即表示可以逃离混境之地。小蓝有一个喷气背包，使用时，可以原地升高 k个单位高度。

坏消息是：

由于小蓝的体力透支，所以只可以往低于当前高度的方向走。喷漆背包燃料不足，只可以最后使用一次。

小蓝可以往上下左右四个方向行走，不消耗能量。

小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，输入 Yes ，反之输出 No 。

输入格式

第 1 行输入三个正整数 n,m 和 k ，n,m 表示混境之地的大小，k 表示使用一次喷气背包可以升高的高度。

第 2 行输入四个正整数 A,B,C,D ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。

第 33 行至第 n+2 行，每行 m 个整数，表示混境之地不同位置的高度。

输出格式

输出数据共一行一个字符串：

若小蓝可以逃离混境之地，则输出 Yes 。若小蓝无法逃离混境之地，则输出 No 。样例输入 5 5 30 1 1 5 5 3 20 13 12 11 19 17 33 72 10 12 23 12 23 9 21 43 23 12 2 21 34 23 12 1

样例输出 Yes

二、代码展示

import java.util.Arrays; import java.util.Scanner; public class ikun { static int n,m,k; static int[][] dp; public static void main(String[] args) { Scanner scan = new Scanner(System.in); n = scan.nextInt(); m = scan.nextInt(); k = scan.nextInt(); int A = scan.nextInt() - 1; int B = scan.nextInt() - 1; int C = scan.nextInt() - 1; int D = scan.nextInt() - 1; int[][] f = new int[n][m]; //地图的二维矩阵 dp = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { f[i][j] = scan.nextInt(); dp[i][j] = -1; } } dfs(A , B, f , 1); if (dp[C][D] == 1){ System.out.println("Yes"); } else System.out.println("No"); } public static void dfs(int a , int b ,int[][] f , int flag){ //flag = 1表示没使用背包 dp[a][b] = 1; int[] dx = {0 , 0 , 1 , -1}; int[] dy = {1 , -1 , 0 , 0}; for (int i = 0; i < 4; i++) { int x = a + dx[i]; int y = b + dy[i]; if (x < 0 || x >= n || y < 0 || y >= m || dp[x][y] == 1) continue; if (f[a][b] >= f[x][y]){ dfs(x , y , f , flag); } else { if (k + f[a][b] >= f[x][y] && flag == 1){ dfs(x , y ,f , 0); } } } } } 代码结构解析 1.变量声明：

n, m, k：分别表示地图的行数、列数和背包的能力值。 dp：二维数组，用于记录已访问的节点，防止重复遍历。

输入处理：读取地图大小、背包能力、起点和终点的坐标（调整为0-based索引）。

初始化地图数据f和访问标记数组dp。

2.DFS函数：

参数：当前位置(a, b)、地图数据f、标志位flag（1表示未使用背包，0表示已使用）。

逻辑：标记当前节点为已访问。遍历四个方向（上下左右），检查相邻节点是否合法且未被访问。直接移动：若相邻节点高度≤当前节点，无需背包即可移动。使用背包移动：若相邻节点高度＞当前节点，且未使用过背包（flag=1），且当前节点高度 +k≥相邻节点高度，则切换为背包模式继续搜索。

结果判断：在主函数中调用DFS后，检查终点是否被访问过，输出"Yes"或"No"。

3.核心逻辑说明

移动规则：

普通移动：当目标节点高度≤当前节点时，可直接移动（无需背包）。背包辅助移动：当目标节点高度＞当前节点时，若尚未使用背包且当前节点高度+k足够覆盖高度差，则使用背包一次允许移动。

背包机制：

每个路径最多只能使用一次背包。一旦使用（flag=0），后续所有移动均不可再用。