1368: Minimum-Cost-to-Make-at-Least-One-Valid-Path-in-a-Grid
Hard

table of contents

This question immediately feels like a breadth-first search question; I do not believe there are any special tricks per se, as it seems like quite a formulaic question.

In my algorithm, we initialize an m x n grid, costGrid, to store the costs at each square we have visited and a queue, currSquares, to keep track of all the squares we need to traverse through at each cost level. The queue starts off with only one square (the one at 0, 0).

While Loop:

Then, while currSquares is not empty, we pop the front element and check if we have visited it or not.

Note, that for every new Square that we visit, we check if it is the bottom-right square (the square at index position [m-1][n-1]). If it is, then we return the cost value immediately.

Once currSquares is empty (there is another if statement inside the while loop to catch this, meaning the initial while loop is still running), then we know we have visited every square possible at this specific cost level. We then swap the queues currSquares and nextSquares around and repeat the steps from the start of the while loop.

Note, this should be enough to solve the question, however, I still added a return costGrid[m-1][n-1] at the end as the non-void function requires a return value in all control paths and just in case I somehow do not manage to visit all squares.

code

class Solution {
private:
    int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    bool isNextSquareValid(vector<vector<int>>& grid, vector<vector<int>>& costGrid, 
                           int &n, int &m, pair<int, int> &coords) {
        pair<int, int> nextSquare = getNextSquare(grid, coords);

        return (nextSquare.first > -1) 
            and (nextSquare.first < n) 
            and (nextSquare.second > -1) 
            and (nextSquare.second < m) 
            and (costGrid[nextSquare.second][nextSquare.first] == -1);
    }
    pair<int, int> getNextSquare(vector<vector<int>>& grid, pair<int, int> &coords) {
        int nextSquareX = coords.first 
                          + direction[grid[coords.second][coords.first]-1][0]
        int nextSquareY = coords.second 
                          + direction[grid[coords.second][coords.first]-1][1];

        return {nextSquareX, nextSquareY};
    }
    void pushValidSquares(queue<pair<int, int>> &currSquares, 
                          vector<vector<int>>& costGrid, 
                          int &n, int &m, pair<int, int> &coords) {
        int x = coords.first;
        int y = coords.second;

        if (x > 0 and costGrid[y][x-1] == -1 and costGrid[y][x] != 2) 
            currSquares.push({x-1, y});
        if (x < n-1 and costGrid[y][x+1] == -1 and costGrid[y][x] != 1) 
            currSquares.push({x+1, y});
        if (y > 0 and costGrid[y-1][x] == -1 and costGrid[y][x] != 4) 
            currSquares.push({x, y-1});
        if (y < m-1 and costGrid[y+1][x] == -1 and costGrid[y][x] != 3) 
            currSquares.push({x, y+1});
    }
public:
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), cost = 0;
        vector<vector<int>> costGrid (m, vector<int>(n, -1));
        queue<pair<int, int>> currSquares, nextSquares;
        currSquares.push({0, 0});

        while (!currSquares.empty()) { 
            pair<int, int> coords = currSquares.front();
            currSquares.pop();
            if (costGrid[coords.second][coords.first] == -1){
                pushValidSquares(nextSquares, costGrid, n, m, coords);
                if (coords.first == n-1 and coords.second == m-1) return cost;
                costGrid[coords.second][coords.first] = cost;
                while (isNextSquareValid(grid, costGrid, n, m, coords)) {
                    coords = getNextSquare(grid, coords);
                    pushValidSquares(nextSquares, costGrid, n, m, coords);
                    if (coords.first == n-1 and coords.second == m-1) return cost;
                    costGrid[coords.second][coords.first] = cost;
                }
            }
            if (currSquares.empty()) {
                swap(currSquares, nextSquares);
                ++cost;
            }
        }
        return costGrid[m-1][n-1];
    }
};

complexity