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

[mah-shamim]

Discussed in #1173

^{Originally posted by mah-shamim January 18, 2025}
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:

1. 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.
2. Do BFS from (0, 0) visit all edges with weight = 0 first. the answer is the distance to (m -1, n - 1).

[mah-shamim]

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) {
    $m = count($grid);
    $n = count($grid[0]);

    // Direction vectors for the signs (right, left, down, up)
    $directions = [
        [0, 1],  // 1: right
        [0, -1], // 2: left
        [1, 0],  // 3: down
        [-1, 0]  // 4: up
    ];

    // Deque for 0-1 BFS
    $deque = new SplQueue();
    $deque->enqueue([0, 0, 0]); // [row, col, cost]

    // Distance array to keep track of the minimum cost to reach each cell
    $dist = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
    $dist[0][0] = 0;

    while (!$deque->isEmpty()) {
        list($x, $y, $cost) = $deque->dequeue();

        // If we've already found a better way, skip this cell
        if ($dist[$x][$y] < $cost) {
            continue;
        }

        // Traverse all 4 directions
        foreach ($directions as $dirIndex => $dir) {
            $nx = $x + $dir[0];
            $ny = $y + $dir[1];
            $newCost = $cost;

            // Check if the new cell is within bounds
            if ($nx >= 0 && $nx < $m && $ny >= 0 && $ny < $n) {
                // If the direction of the current cell matches the intended movement
                if ($grid[$x][$y] == $dirIndex + 1) {
                    $newCost = $cost; // No additional cost
                } else {
                    $newCost = $cost + 1; // Modify the direction with cost 1
                }

                // Update distance and add to deque
                if ($newCost < $dist[$nx][$ny]) {
                    $dist[$nx][$ny] = $newCost;
                    if ($newCost == $cost) {
                        $deque->unshift([$nx, $ny, $newCost]); // Add to front
                    } else {
                        $deque->enqueue([$nx, $ny, $newCost]); // Add to back
                    }
                }
            }
        }
    }

    // Return the minimum cost to reach the bottom-right corner
    return $dist[$m - 1][$n - 1];
}

// 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:

1. 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].

2. 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.

3. 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).

4. 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.

5. 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.