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

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

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

 

class Solution {
public:
    vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    int dp[101][101];
    
    void backtrack(vector<vector<int>>& grid, int y, int x, int cost){
        int n = grid.size();
        int m = grid[0].size();
        
        if(y >= n || y < 0 || x >= m || x < 0){
            return;
        }
        
        int &ret = dp[y][x];
        if(ret != -1 && ret <= cost) return;
        ret = cost;
        
        if(dp[n - 1][m - 1] != -1 && dp[n - 1][m - 1] <= ret) return;
        
        if(n - 1 == y && m - 1 == x){
            return;
        }
        
        int nextY = y + directions[grid[y][x] - 1][0];
        int nextX = x + directions[grid[y][x] - 1][1];
        
        if(nextY < n && nextY >= 0 && nextX < m && nextX >= 0){
            backtrack(grid, nextY, nextX, cost);
        }
        
        for(int i = 0; i < 4; i++){
            int nextY = y + directions[i][0];
            int nextX = x + directions[i][1];
            
            if(nextY >= n || nextY < 0 || nextX >= m || nextX < 0){
                continue;
            }
            
            if(grid[y][x] - 1 == i){
                continue;
            } else {
                backtrack(grid, nextY, nextX, cost + 1);
            }
        }
    }
    
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        memset(dp, -1, sizeof(dp));
        backtrack(grid, 0, 0, 0);
        return dp[n - 1][m - 1];
    }
};

 

 

어렵다... TLE... 킄

 

 

 

class Solution {
public:
    vector<vector<int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    void dfs(vector<vector<int>>& grid, int y, int x, vector<vector<int>>& dp, int cost, queue<pair<int, int>>& que){
        int n = grid.size(), m = grid[0].size();
        if(y >= n || y < 0 || x >= m || x < 0 || dp[y][x] != INT_MAX){
            return;
        }
        dp[y][x] = cost;
        que.push({y, x});
        int nextDir = grid[y][x] - 1;
        dfs(grid, y + dir[nextDir][0], x + dir[nextDir][1], dp, cost, que);
    }
    
    int minCost(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
        int cost = 0;
        queue<pair<int, int>> que;
        dfs(grid, 0, 0, dp, cost, que);
        
        while(!que.empty()){
            cost++;
            int len = que.size();
            while(len--){
                int y = que.front().first;
                int x = que.front().second;
                que.pop();
                for(int i = 0; i < 4; i++){
                    dfs(grid, y + dir[i][0] , x + dir[i][1], dp, cost, que);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};