fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define PI 3.14159265359
  4. #define DP(x, y) memset(x, y, sizeof x)
  5. #define all(x) x.begin(), x.end()
  6. #define read(x) freopen("x", "r", stdin);
  7. #define write(x) freopen("x", "w", stdout);
  8.  
  9. using namespace std;
  10.  
  11. ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
  12. ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
  13. ll nC2(ll n) { return (n)*(n-1)/2; }
  14. ll summing(ll n) { return (n)*(n+1); }
  15.  
  16. int Paths(int i, int j, int n, int m, vector<vector<char>>&grid, vector<vector<bool>>&vis, vector<vector<int>>&dp) {
  17.  
  18.     if (i == n && j == m) {
  19.         return 1;
  20.     }
  21.     if (i > n || j > m || i == 0 || j == 0) {
  22.         return 0;
  23.     }
  24.     if ( grid[i][j] == '*' || vis[i][j] ) {
  25.         return 0;
  26.     }
  27.     if (~dp[i][j]) {
  28.         return dp[i][j];
  29.     }
  30.  
  31.     dp[i][j] = 0;
  32.  
  33.     vis[i][j] = 1;
  34.     int x = Paths(i+1, j, n, m, grid, vis, dp);
  35.     int y = Paths(i, j+1, n, m, grid, vis, dp);
  36.     vis[i][j] = 0;
  37.  
  38.  
  39.     dp[i][j] = x+y;
  40.  
  41.     return (dp[i][j]);
  42.  
  43. }
  44.  
  45. void solve() {
  46.  
  47.     int n,m; cin >> n >> m;
  48.  
  49.     vector<pair<int,int>> breaking;
  50.     vector<vector<char>> grid(n+1, vector<char>(m+1, '.'));
  51.     vector<vector<bool>> vis(n+1, vector<bool>(m+1, 0));
  52.  
  53.     vector<vector<int>> dp(n+1, vector<int>(m+1, -1));
  54.  
  55.     cin.ignore();
  56.  
  57.     for (int i=0; i<n; i++) {
  58.  
  59.         string s, row, col;
  60.         getline(cin, s);
  61.  
  62.         stringstream ss(s);
  63.  
  64.         ss >> row;
  65.  
  66.         while (ss >> col) {
  67.             breaking.push_back({stoi(row), stoi(col)});
  68.         }
  69.     }
  70.  
  71.     for (auto i:breaking) {
  72.         grid[i.first][i.second] = '*';
  73.     }
  74.  
  75.     cout << Paths(1,1,n,m,grid,vis,dp);
  76.  
  77. }
  78.  
  79. int main()
  80. {
  81.     ios::sync_with_stdio(false);
  82.     cin.tie(nullptr), cout.tie(nullptr);
  83.  
  84.     ll t=1; cin >> t;
  85.     for (int ii=1; ii<=t; ii++) {
  86.         solve();
  87.         if (ii != t) cout << "\n\n";
  88.     }
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0s 5276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/xCraC6
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!