1368. Minimum Cost to Make at Least One Valid Path in a Grid

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

1368. Minimum Cost to Make at Least One Valid Path in a Grid

Difficulty: Hard

Topics: Array, Breadth-First Search, Graph, Heap (Priority Queue), Matrix, Shortest Path

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])

Notice that there could be some signs on the cells of the grid that point outside the grid.

You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.

You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.

Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0). The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0)
change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3)
change the arrow to down with cost = 1 --> (3, 3) The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 4

Hint:

Build a graph where grid[i][j] is connected to all the four side-adjacent cells with weighted edge. the weight is 0 if the sign is pointing to the adjacent cell or 1 otherwise.
Do BFS from (0, 0) visit all edges with weight = 0 first. the answer is the distance to (m -1, n - 1).

Solution:

We can use the 0-1 BFS approach. The idea is to traverse the grid using a deque (double-ended queue) where the cost of modifying the direction determines whether a cell is added to the front or back of the deque. The grid is treated as a graph where each cell has weighted edges based on whether its current direction matches the movement to its neighbors.

Let's implement this solution in PHP: 1368. Minimum Cost to Make at Least One Valid Path in a Grid

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function minCost($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Test Cases
$grid1 = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($grid1) . "\n"; // Output: 3

$grid2 = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($grid2) . "\n"; // Output: 0

$grid3 = [[1,2],[4,3]];
echo minCost($grid3) . "\n"; // Output: 1
?>

Explanation:

Direction Mapping: Each direction (1 for right, 2 for left, 3 for down, 4 for up) is mapped to an array of movement deltas [dx, dy].
0-1 BFS:
- A deque is used to prioritize cells with lower costs. Cells that do not require modifying the direction are added to the front (unshift), while those that require a modification are added to the back (enqueue).
- This ensures that cells are processed in increasing order of cost.
Distance Array: A 2D array $dist keeps track of the minimum cost to reach each cell. It is initialized with PHP_INT_MAX for all cells except the starting cell (0, 0).
Edge Weights:
- If the current cell's sign matches the intended direction, the cost remains the same.
- Otherwise, modifying the direction incurs a cost of 1.
Termination: The loop terminates once all cells have been processed. The result is the value in $dist[$m - 1][$n - 1], representing the minimum cost to reach the bottom-right corner.

Complexity:

Time Complexity: O(m × n), since each cell is processed once.
Space Complexity: O(m × n), for the distance array and deque.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

Print Share Comment Cite Upload Translate Updates

APA

MD ARIFUL HAQUE | Sciencx (2025-01-18T15:26:53+00:00) 1368. Minimum Cost to Make at Least One Valid Path in a Grid. Retrieved from https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

MLA

" » 1368. Minimum Cost to Make at Least One Valid Path in a Grid." MD ARIFUL HAQUE | Sciencx - Saturday January 18, 2025, https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

HARVARD

MD ARIFUL HAQUE | Sciencx Saturday January 18, 2025 » 1368. Minimum Cost to Make at Least One Valid Path in a Grid., viewed ,<https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/>

VANCOUVER

MD ARIFUL HAQUE | Sciencx - » 1368. Minimum Cost to Make at Least One Valid Path in a Grid. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

CHICAGO

" » 1368. Minimum Cost to Make at Least One Valid Path in a Grid." MD ARIFUL HAQUE | Sciencx - Accessed . https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

IEEE

" » 1368. Minimum Cost to Make at Least One Valid Path in a Grid." MD ARIFUL HAQUE | Sciencx [Online]. Available: https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/. [Accessed: ]

rf:citation

» 1368. Minimum Cost to Make at Least One Valid Path in a Grid | MD ARIFUL HAQUE | Sciencx | https://www.scien.cx/2025/01/18/1368-minimum-cost-to-make-at-least-one-valid-path-in-a-grid/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Explanation:

Complexity:

Related Posts