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

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.

• if we have, then we continue to the next element
• if we have not, then we traverse through the directed path, updating costGrid at each square and stopping only if we go out of bounds or traverse to a square we have visited before. At every square, we also check for any neighbouring squares that have not been visited and is not being directly pointed to by the original square and append it to a seperate queue, nextSquares.

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

• time: O(mn)
• space: O(mn)