Untitled
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]; } };