fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define debug(a) cerr << #a << " = " << (a) << nl;
  4. #define ll long long
  5. #define int long long
  6. #define nl '\n'
  7.  
  8. const int N = 1e3+5;
  9.  
  10. int n, m;
  11. int a[N][N];
  12.  
  13. // path count, defuse 
  14. pair<int, int> go(int i, int j, int from, int cons) {
  15.     if(i == 1 and j == 1) return make_pair(1, 0);
  16.     if(i < 1 or j < 1) return make_pair(0, 1e8);
  17.     int def = 0;
  18.     if(from == 1) {
  19.         if(cons == 1)  def += a[i-1][j] + a[i][j-1];
  20.         else def += a[i-1][j] + a[i][j+1] + a[i][j-1];
  21.     }
  22.     else {
  23.         if(cons == 1) def += a[i][j-1] + a[i-1][j];
  24.         else def += a[i-1][j] + a[i+1][j] + a[i-1][j];
  25.     }
  26.     // cerr << i << " " << j << ' ' << from << ' ' << cons << " " << def << endl;
  27.  
  28.     auto [p1, q1] = go(i-1, j, 1, 1+(from==1)); // top
  29.     auto [p2, q2] = go(i, j-1, 0, 1+(from==0)); // left
  30.  
  31.     if(q1 == q2) return make_pair(p1+p2, q1+def);
  32.     else if(q1 < q2) return make_pair(p1, q1+def);
  33.     else return make_pair(p2, q2+def);
  34. }
  35.  
  36. void jAVA()
  37. {
  38.     cin >> n >> m;
  39.     for(int i=0; i<=n+2;++i) {
  40.         for(int j=0; j<=m+2;++j) {
  41.             a[i][j] = 0;
  42.         }
  43.     }
  44.     for (int i = 1; i <= n; i++) {
  45.         string s; cin >> s;
  46.         for (int j = 0; j < m; j++) {
  47.             if(s[j] == '#') a[i][j+1] = 1;
  48.         }
  49.     }
  50.     a[1][1] = 0;
  51.     a[1][2] = 0;
  52.     a[2][1] = 0;
  53.  
  54.     a[n][m] = 0;
  55.     a[n-1][m] = 0;
  56.     a[n][m-1] = 0;
  57.     // for(int i=1; i<=n;++i) {
  58.     //     for(int j=1; j<=m;++j) {
  59.     //         cout << a[i][j] << ' ';
  60.     //     }
  61.     //     cout << '\n';
  62.     // }
  63.     cout << go(n,m,0,0).first << nl;
  64. }
  65.  
  66. int32_t main()
  67. {
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(nullptr); cout.tie(nullptr);
  70.  
  71.     int t = 1, cs = 0;
  72.     cin >> t;
  73.     while (t--){
  74.         // cout << "Case " << ++cs << ": ";
  75.         jAVA();
  76.     }
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
1
3 3
.##
.#.
###
stdout
copy 
4
https://ideone.com/hJct74
language:
C++14 (gcc 8.3)
created:
12 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!