1
class Tuple {
2

3
  int distance;
4

5
  int row;
6

7
  int col;
8

9
  Tuple(int distance, int row, int col) {
10

11
    this.distance = distance;
12

13
    this.row = row;
14

15
    this.col = col;
16
  }
17
}
18

19
class Solution {
20

21
  public int minimumEffortPath(int[][] heights) {
22

23
    // Create a min heap based on the distance
24

25
    PriorityQueue<Tuple> minHeap = new PriorityQueue<>((x, y) -> x.distance - y.distance);
26

27
    int rows = heights.length;
28

29
    int cols = heights[0].length;
30

31
    // Create a 2D array to store the minimum effort to reach each cell
32

33
    int effort[][] = new int[rows][cols];
34

35
    // Initialize all efforts to maximum initially
36

37
    for (int i = 0; i < rows; i++) {
38

39
      Arrays.fill(effort[i], Integer.MAX_VALUE);
40
    }
41

42
    effort[0][0] = 0; // Initial effort at the starting cell
43

44
    // Add the starting cell to the min heap
45

46
    minHeap.add(new Tuple(0, 0, 0));
47

48
    // Arrays to represent row and column changes for 4 directions
49

50
    int dr[] = {-1, 0, 1, 0}; // Up, Right, Down, Left
51

52
    int dc[] = {0, 1, 0, -1};
53

54
    while (!minHeap.isEmpty()) {
55

56
      Tuple current = minHeap.poll(); // Get the cell with the minimum effort
57

58
      int distance = current.distance;
59

60
      int row = current.row;
61

62
      int col = current.col;
63

64
      if (row == rows - 1 && col == cols - 1) {
65

66
        return distance; // If reached the destination, return the effort
67
      }
68

69
      // Explore each of the 4 possible directions
70

71
      for (int i = 0; i < 4; i++) {
72

73
        int newRow = row + dr[i]; // Calculate new row index
74

75
        int newCol = col + dc[i]; // Calculate new column index
76

77
        // Check if the new cell is within bounds
78

79
        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
80

81
          // Calculate the new effort based on the maximum of height difference and current effort
82

83
          int newEffort = Math.max(Math.abs(heights[row][col] - heights[newRow][newCol]), distance);
84

85
          // If the new effort is less than the stored effort for the cell, update and add to heap
86

87
          if (newEffort < effort[newRow][newCol]) {
88

89
            effort[newRow][newCol] = newEffort;
90

91
            minHeap.add(
92
                new Tuple(newEffort, newRow, newCol)); // Add to heap for further exploration
93
          }
94
        }
95
      }
96
    }
97

98
    return 0; // This value should be replaced with the actual minimum effort
99
  }
100
}