Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
1.1 kB
5
Indexable
Never
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        const auto& m = obstacleGrid.size();
        const auto& n = obstacleGrid[0].size();

        vector<vector<int>> dp(m, vector<int>(n));
        queue<pair<int, int>> q;

        if (obstacleGrid[0][0] != 1)
        {
            dp[0][0] = 1;
            q.push({0, 0});
        }

        while(q.size())
        {
            const auto& i = q.front().first;
            const auto& j = q.front().second;

            if (i + 1 < m && obstacleGrid[i + 1][j] == 0)
            {
                if (dp[i + 1][j] == 0)
                {
                    q.push({i + 1, j});
                }
                dp[i + 1][j] += dp[i][j];
            }

            if (j + 1 < n && obstacleGrid[i][j + 1] == 0)
            {
                if (dp[i][j + 1] == 0)
                {
                    q.push({i, j + 1});
                }
                dp[i][j + 1] += dp[i][j];
            }

            q.pop();
        }

        return dp[m - 1][n - 1];
    }
};