diff options
author | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
---|---|---|
committer | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
commit | dc1f0c4c0096013799416664894c5194dc7e1f52 (patch) | |
tree | 2f5d235f778cd720f4c39ec3e56b77ba6d99f375 /works/life/2020-algorithm-contest/code/4.cpp | |
parent | 7299d424d90b1effb6db69e3476ddd5af72eeba4 (diff) | |
download | crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.gz crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.bz2 crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.zip |
chore(store): move everything to store.
Diffstat (limited to 'works/life/2020-algorithm-contest/code/4.cpp')
-rw-r--r-- | works/life/2020-algorithm-contest/code/4.cpp | 71 |
1 files changed, 0 insertions, 71 deletions
diff --git a/works/life/2020-algorithm-contest/code/4.cpp b/works/life/2020-algorithm-contest/code/4.cpp deleted file mode 100644 index 4ee94cb..0000000 --- a/works/life/2020-algorithm-contest/code/4.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#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; -} |