Understand Minimum Cost to Make a Valid Path in a Grid Problem

Problem Name: Minimum Cost to Make a Valid Path in a Grid

Problem Description:

Problem Summary: Minimum Cost to Make a Valid Path in a Grid

You are given a grid with m x n dimensions, where each cell contains an arrow pointing to one of four directions:

Right (1): Move to the cell on the right.
Left (2): Move to the cell on the left.
Down (3): Move to the cell below.
Up (4): Move to the cell above.

You start at the top-left corner (0, 0) and aim to reach the bottom-right corner (m-1, n-1) by following the arrows.
If necessary, you can modify the arrow in a cell at a cost of 1.
The goal is to calculate the minimum cost required to create at least one valid path from the start to the end of the grid.

Examples:

Input: [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

Output: 3

Explanation: Modify arrows in 3 cells to create a valid path from (0, 0) to (3, 3).
Input: [[1,1,3],[3,2,2],[1,1,4]]

Output: 0
Explanation: A valid path already exists without any modifications.
Input: [[1,2],[4,3]]
Output: 1
Explanation: Modify one cell's arrow to create a valid path.

Constraints:

1 <= m, n <= 100
Each cell contains a value from 1 to 4.

Category:
Leetcode Problem of the Day
DP
Graphs

Programming Language:
Java

Reference Link:

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

Main Function is not defined.

Helper Function:

Input: [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]

Output: 3

int INF = (int) 1e9;

int[][] DIR = new int[ ][ ]{{0,1} , {0 , -1}, {1,0 }, {-1 , 0} };

public static int minCost( int[][] grid) {

int m = grid.length;

n = grid[0].length;

cost = 0;

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++){

Arrays.fill(dp[i], INF);

}//Loop End

Queue<int[]> bfs = new LinkedList<>();

dfs(grid, 0, 0, dp, cost, bfs);

while (!bfs.isEmpty()) {

cost++;

for (int size = bfs.size(); size > 0; size--) {

int[] top = bfs.poll();

int r = top[0];

int c = top[1];

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

dfs(grid, r + DIR[i][0], c + DIR[i][1], dp, cost, bfs);

}//Loop End

return dp[m - 1][n - 1];

}//function end

Utility Functions and Global variables:

public static void dfs(int[][] grid, int r, int c, int[][] dp, int cost, Queue<int[]> bfs) {

int m = grid.length;

int n = grid[0].length;

if (r < 0 || r >= m || c < 0 || c >= n || dp[r][c] != INF){

return;

}

dp[r][c] = cost;

bfs.offer(new int[]{r, c});

int nextDir = grid[r][c] - 1;

dfs(grid, r + DIR[nextDir][0], c + DIR[nextDir][1], dp, cost, bfs);

return