一、問題描述

小藍有一天誤入了一個混境之地。

好消息是：他誤打誤撞拿到了一張地圖，并從中獲取到以下信息：

1. 混境之地是一個n?m?大小的矩陣，其中第?i?行第?j 列的的點?h i j??表示第?i?行第 j?列的高度。
2. 他現在所在位置的坐標為?(A,B)?，而這個混境之地出口的坐標為?(C,D) ，當站在出口時即表示可以逃離混境之地。
3. 小藍有一個噴氣背包，使用時，可以原地升高?k個單位高度。

壞消息是：

1. 由于小藍的體力透支，所以只可以往低于當前高度的方向走。
2. 噴漆背包燃料不足，只可以最后使用一次。

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

小藍想知道他能否逃離這個混境之地，如果可以逃離這里，輸入?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），后續所有移動均不可再用。

DFS特性：

? ? 遞歸探索所有可能的路徑，利用dp數組剪枝已訪問節點，避免循環。

總結
該代碼通過DFS遍歷所有可能的路徑，結合背包機制解決特定高度差的移動問題，最終判斷是否存在符合條件的路徑。核心在于合理利用標志位控制背包使用，并通過剪枝避免重復計算。