18_Minimum_Cost.cpp

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

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

const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
class Solution
{
public:
    int minCost(vector<vector<int>> &grid)
    {
        int r = grid.size(), c = grid[0].size();
        vector<vector<int>> dist(r, vector<int>(c, INT_MAX));
        deque<pair<int, int>> dq;
        dq.emplace_front(0, 0);
        dist[0][0] = 0;

        while (!dq.empty())
        {
            auto [x, y] = dq.front();
            dq.pop_front();
            for (int i = 0; i < 4; ++i)
            {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < r && ny >= 0 && ny < c)
                {
                    int cost = (i + 1 == grid[x][y]) ? 0 : 1;
                    if (dist[x][y] + cost < dist[nx][ny])
                    {
                        dist[nx][ny] = dist[x][y] + cost;
                        if (cost == 0)
                        {
                            dq.emplace_front(nx, ny);
                        }
                        else
                        {
                            dq.emplace_back(nx, ny);
                        }
                    }
                }
            }
        }
        return dist[r - 1][c - 1];
    }
};

/*
This code implements a solution to find the minimum cost path in a grid using a modified version of Dijkstra's algorithm with a 0-1 BFS approach:

1. dx[] and dy[] arrays define the 4 possible directions (right, left, down, up)

2. The minCost function:
 - Takes a grid as input
 - Creates a distance matrix initialized with INT_MAX
 - Uses a deque for BFS traversal
 - Starts from position (0,0)

3. Main algorithm:
 - For each cell, explores all 4 directions
 - If the direction matches grid value, cost is 0; otherwise cost is 1
 - Uses deque to prioritize zero-cost moves (added to front)
 - Adds cost-1 moves to back of deque
 - Updates distances when a shorter path is found

4. The solution efficiently finds minimum cost to reach bottom-right cell
 by prioritizing paths that follow existing directions (cost 0)
 over paths requiring direction changes (cost 1)
*/