1 files changed, 71 insertions, 0 deletions
diff --git a/store/works/life/2020-algorithm-contest/code/4.cpp b/store/works/life/2020-algorithm-contest/code/4.cpp
new file mode 100644
index 0000000..4ee94cb
--- /dev/null
+++ b/store/works/life/2020-algorithm-contest/code/4.cpp
@@ -0,0 +1,71 @@
+#include <iostream>
+#include <vector>
+
+int calc(std::vector<std::vector<int>> &obstacleGrid)
+{
+
+    int R = obstacleGrid.size();
+    int C = obstacleGrid[0].size();
+
+    // If the starting cell has an obstacle, then simply return as there would be
+    // no paths to the destination.
+    if (obstacleGrid[0][0] == 1)
+    {
+        return 0;
+    }
+
+    // Number of ways of reaching the starting cell = 1.
+    obstacleGrid[0][0] = 1;
+
+    // Filling the values for the first column
+    for (int i = 1; i < R; i++)
+    {
+        obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
+    }
+
+    // Filling the values for the first row
+    for (int i = 1; i < C; i++)
+    {
+        obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
+    }
+
+    // Starting from cell(1,1) fill up the values
+    // No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
+    // i.e. From above and left.
+    for (int i = 1; i < R; i++)
+    {
+        for (int j = 1; j < C; j++)
+        {
+            if (obstacleGrid[i][j] == 0)
+            {
+                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
+            }
+            else
+            {
+                obstacleGrid[i][j] = 0;
+            }
+        }
+    }
+
+    // Return value stored in rightmost bottommost cell. That is the destination.
+    return obstacleGrid[R - 1][C - 1];
+}
+
+int main()
+{
+    int row, column, bs;
+    std::cin >> row >> column >> bs;
+
+    std::vector<std::vector<int>> grid(row, std::vector<int>(column, 0));
+
+    for (int i = 0; i < bs; i++)
+    {
+        int r, c;
+        std::cin >> r >> c;
+        grid[r][c] = 1;
+    }
+
+    std::cout << calc(grid);
+
+    return 0;
+}