fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr unsigned int MOD = 1e9 + 7;
  5.  
  6.  
  7. class HGrid1 {
  8. public:
  9. int totalPath(vector<vector<char>>& grid, int rows, int cols) {
  10. vector<vector<int>> dp(rows, vector<int>(cols, 0));
  11.  
  12. dp[0][0] = 1;
  13.  
  14. for(int i = 1; i < cols; ++i) {
  15. dp[0][i] = grid[0][i] == '#' ? 0 : dp[0][i-1];
  16. }
  17.  
  18.  
  19. for(int r = 1; r < rows; ++r) {
  20. dp[r][0] = grid[r][0] == '#' ? 0 : dp[r-1][0];
  21. for(int c = 1; c < cols; ++c) {
  22. dp[r][c] = grid[r][c] == '#' ? 0 : (dp[r-1][c]+dp[r][c-1])%MOD;
  23. }
  24. }
  25.  
  26. return dp[rows-1][cols-1];
  27. }
  28. };
  29.  
  30.  
  31. int main() {
  32. int rows, cols;
  33. cin >> rows >> cols;
  34. vector<vector<char>> grid(rows, vector<char>(cols));
  35. for(int r = 0; r < rows; ++r) {
  36. for(int c = 0; c < cols; ++c) {
  37. cin >> grid[r][c];
  38. }
  39. }
  40.  
  41. HGrid1 obj;
  42. cout << obj.totalPath(grid, rows, cols) << endl;
  43. return 0;
  44. }
Success #stdin #stdout 0.01s 5316KB
stdin
20 20
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
stdout
345263555