leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |
commit169c8dcb61f73078f5dba6ab2311594d039608e2
parentfe5cef57411cfa6b4ca76ea452efde89b1e50dcc
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateSat, 4 Feb 2023 13:51:30 +0100

Dynamic Programming I: Day 15

Diffstat:
AProblems/0063.cpp|+++++++++++++++++++++++++++++
MREADME.md|+

2 files changed, 30 insertions(+), 0 deletions(-)

diff --git a/Problems/0063.cpp b/Problems/0063.cpp

@@ -0,0 +1,29 @@

class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
int n = obstacleGrid.size(), m = obstacleGrid[0].size();
vector<vector<long>> mat(n, vector<long>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (obstacleGrid[i][j]) mat[i][j] = -1;
if (mat[n - 1][m - 1] == -1) return 0;
if (mat[0][0] == -1) return 0;
queue<pair<int, int>> q;
q.push({n - 1, m - 1}), mat[n - 1][m - 1] = 1;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (x - 1 >= 0 && mat[x - 1][y] != -1) {
mat[x - 1][y] += mat[x][y];
if (mat[x - 1][y] == mat[x][y]) q.push({x - 1, y});
}
if (y - 1 >= 0 && mat[x][y - 1] != -1) {
mat[x][y - 1] += mat[x][y];
if (mat[x][y - 1] == mat[x][y]) q.push({x, y - 1});
}
}
return (int)mat[0][0];
}
};

diff --git a/README.md b/README.md

@@ -59,6 +59,7 @@ for solving problems.

| 0059 | Medium | [Spiral Matrix II](Problems/0059.cpp) |
| 0061 | Medium | [Rotate List](Problems/0061.cpp) |
| 0062 | Medium | [Unique Paths](Problems/0062.cpp) |
| 0063 | Medium | [Unique Paths II](Problems/0063.cpp) |
| 0066 | Easy | [Plus One](Problems/0066.cpp) |
| 0067 | Easy | [Add Binary](Problems/0067.cpp) |
| 0070 | Easy | [Climbing Stairs](Problems/0070.cpp) |