leetcode

commit 1f1e18fa41a019e8aee4f354dbfb525653db6ba4
parent 64049a209a92c1e5921a261bffefdcb6dbcea74d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 12 Aug 2023 10:56:32 +0200

Improved Daily Problem

Diffstat:
M
Problems/0063.cpp
 | 
37
++++++++++++++++++-------------------

1 file changed, 18 insertions(+), 19 deletions(-)
diff --git a/Problems/0063.cpp b/Problems/0063.cpp
@@ -1,29 +1,28 @@
 class Solution {
 public:
   int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
+    int dp[101][101] = {0};
     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;
+    for (int i = 0, flag = 0; i < n; i++) {
+      if (flag || obstacleGrid[i][0])
+        flag = true;
+      else
+        dp[i][0] = 1;
+    }
 
-    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});
+    for (int i = 0, flag = 0; i < m; i++) {
+      if (flag || obstacleGrid[0][i])
+        flag = true;
+      else
+        dp[0][i] = 1;
+    }
+
+    for (int i = 1; i < n; i++) {
+      for (int j = 1; j < m; j++) {
+        if (obstacleGrid[i][j] != 1) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
       }
     }
-    return (int)mat[0][0];
+    return dp[n - 1][m - 1];
   }
 };