fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll int
  3. #define ld long double
  4. #define fi first
  5. #define se second
  6. #define pii pair<ll ,ll>
  7. #define nmax int(2e3+7)
  8. #define oo (ll)(1e18)
  9. #define MOD (ll)(998244353)
  10. #define pb push_back
  11. #define m_p make_pair
  12. #define pro "pushingrocks"
  13. #define Kietej ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  14. using namespace std;
  15. ll m,n;
  16. char a[nmax][nmax];
  17.  
  18. namespace Sub1
  19. {
  20.     ll res=0,dd[nmax][nmax];
  21.     ll dx[]={1,0};
  22.     ll dy[]={0,1};
  23.     bool Check(ll i,ll j)
  24.     {
  25.         return (i>=1 && i<=m && j>=1 && j<=n && dd[i][j]!=1);
  26.     }
  27.     void DFS(ll i,ll j)
  28.     {
  29.         if(i==m && j==n)
  30.         {
  31.             res=(res+1)%MOD;
  32.             return ;
  33.         }
  34.         dd[i][j]=1;
  35.         for(ll k=0; k<2; k++)
  36.         {
  37.             ll nx=i+dx[k];
  38.             ll ny=j+dy[k];
  39.             if(!Check(nx,ny))continue;
  40.             if(a[nx][ny]=='.')DFS(nx,ny);
  41.             else if(a[nx][ny]=='R')
  42.             {
  43.                 vector<vector<char>> backup(m+1,vector<char>(n+1));
  44.                 ll vt=-1;
  45.                 if(k==0)
  46.                 {
  47.                     for(ll row=nx; row<=m; row++)
  48.                     {
  49.                         if(a[row][ny]=='.')
  50.                         {
  51.                             vt=row;break;
  52.                         }
  53.                     }
  54.                     if(vt==-1)continue;
  55.                     for(ll ii=1; ii<=m; ii++)for(ll jj=1; jj<=n; jj++)backup[ii][jj]=a[ii][jj];
  56.                     for(ll row=vt; row>nx; row--)a[row][ny]=a[row-1][ny];
  57.                     a[nx][ny]='.'; DFS(nx,ny);
  58.                     for(ll ii=1; ii<=m; ii++)for(ll jj=1; jj<=n; jj++)a[ii][jj]=backup[ii][jj];
  59.                 }
  60.                 else
  61.                 {
  62.                     for(ll col=ny; col<=n; col++)
  63.                     {
  64.                         if(a[nx][col]=='.')
  65.                         {
  66.                             vt=col;break;
  67.                         }
  68.                     }
  69.                     if(vt==-1)continue;
  70.                     for(ll ii=1; ii<=m; ii++)for(ll jj=1; jj<=n; jj++)backup[ii][jj]=a[ii][jj];
  71.                     for(ll col=vt; col>ny; col--)a[nx][col]=a[nx][col-1];
  72.                     a[i][j+1]='.';DFS(nx,ny);
  73.                     for(ll ii=1; ii<=m; ii++)for(ll jj=1; jj<=n; jj++)a[ii][jj]=backup[ii][jj];
  74.                 }
  75.             }
  76.         }
  77.         dd[i][j]=0;
  78.     }
  79.     void Solve()
  80.     {
  81.         DFS(1,1);
  82.         cout<<res;
  83.     }
  84. }
  85. namespace Sub2
  86. {
  87.     ll cntR2[nmax];
  88.     void Solve()
  89.     {
  90.         if(n==2)
  91.         {
  92.             ll cntR1=0;
  93.             for(ll i=1; i<=m; i++)
  94.             {
  95.                 cntR2[i]=cntR2[i-1];
  96.                 if(a[i][1]=='R')cntR1++;
  97.                 if(a[i][2]=='R')cntR2[i]++;
  98.             }
  99.             ll dem=0;
  100.             for(ll i=1; i<=m-cntR1; i++)
  101.             {
  102.                 if(a[i][2]=='R')continue;
  103.                 if(cntR2[m]-cntR2[i]<=0)dem++;
  104.             }
  105.             cout<<dem%MOD;
  106.         }
  107.         else if(m==2)
  108.         {
  109.             ll cntR1=0;
  110.             for(ll i=1; i<=n; i++)
  111.             {
  112.                 cntR2[i]=cntR2[i-1];
  113.                 if(a[1][i]=='R')cntR1++;
  114.                 if(a[2][i]=='R')cntR2[i]++;
  115.             }
  116.             ll dem=0;
  117.             for(ll i=1; i<=n-cntR1; i++)
  118.             {
  119.                 if(a[2][i]=='R')continue;
  120.                 if(cntR2[n]-cntR2[i]<=0)dem++;
  121.             }
  122.             cout<<dem%MOD;
  123.         }
  124.     }
  125. }
  126.  
  127. namespace Sub3
  128. {
  129.     ll R[nmax][nmax],D[nmax][nmax];
  130.     ll ColRocks[nmax][nmax],RowRocks[nmax][nmax];
  131.     ll DownLimit[nmax][nmax],RightLimit[nmax][nmax];
  132.     ll addDown[nmax][nmax],addRight[nmax][nmax];
  133.     void Solve()
  134.     {
  135.         for(ll i=m; i>=1; i--)
  136.         {
  137.             for(ll j=n; j>=1; j--)
  138.             {
  139.                 RowRocks[i][j]=RowRocks[i][j+1];
  140.                 ColRocks[i][j]=ColRocks[i+1][j];
  141.                 if(a[i][j]=='R')
  142.                 {
  143.                     RowRocks[i][j]++;
  144.                     ColRocks[i][j]++;
  145.                 }
  146.             }
  147.         }
  148.         for(ll i=1; i<=m; i++)
  149.         {
  150.             for(ll j=1; j<=n; j++)
  151.             {
  152.                 if(m-i-ColRocks[i+1][j]>0)DownLimit[i][j]=m-ColRocks[i+1][j];
  153.                 else DownLimit[i][j]=i;
  154.                 if(n-j-RowRocks[i][j+1]>0)RightLimit[i][j]=n-RowRocks[i][j+1];
  155.                 else RightLimit[i][j]=j;
  156.             }
  157.         }
  158.         D[1][1]=1;
  159.         R[1][1]=1;
  160.         for(ll i=1; i<=m; i++)
  161.         {
  162.             for(ll j=1; j<=n; j++)
  163.             {
  164.                 addDown[i][j]=(addDown[i][j]+addDown[i-1][j])%MOD;
  165.                 addRight[i][j]=(addRight[i][j]+addRight[i][j-1])%MOD;
  166.                 R[i][j]=(R[i][j]+addRight[i][j])%MOD;
  167.                 D[i][j]=(D[i][j]+addDown[i][j])%MOD;
  168.                 ll d1=DownLimit[i][j],d2=RightLimit[i][j];
  169.  
  170.                 if(d1>i)
  171.                 {
  172.                     addDown[i+1][j]=(addDown[i+1][j]+R[i][j])%MOD;
  173.                     addDown[d1+1][j]=((addDown[d1+1][j]-R[i][j])%MOD+MOD)%MOD;
  174.                 }
  175.                 if(d2>j)
  176.                 {
  177.                     addRight[i][j+1]=(addRight[i][j+1]+D[i][j])%MOD;
  178.                     addRight[i][d2+1]=((addRight[i][d2+1]-D[i][j])%MOD+MOD)%MOD;
  179.                 }
  180.             }
  181.         }
  182.         cout<<(R[m][n]+D[m][n])%MOD;
  183.     }
  184.  
  185. }
  186.  
  187. int main()
  188. {
  189.     Kietej
  190.     if (fopen(pro ".inp", "r"))
  191.     {
  192.         freopen(pro ".inp", "r", stdin);
  193.         freopen(pro ".out", "w", stdout);
  194.     }
  195.     cin>>m>>n;
  196.     for(ll i=1; i<=m; i++)
  197.     {
  198.         for(ll j=1; j<=n; j++)
  199.         {
  200.             cin>>a[i][j];
  201.         }
  202.     }
  203.     if(a[1][1]=='R' || a[m][n]=='R')
  204.     {
  205.         cout<<0;
  206.         return 0;
  207.     }
  208.     if(m==1 && n==1)
  209.     {
  210.         cout<<1;
  211.         return 0;
  212.     }
  213.     if(n<=10 && m<=10)
  214.     {
  215.         Sub1::Solve();
  216.         return 0;
  217.     }
  218.     else if(n==2 || m==2)
  219.     {
  220.         Sub2::Solve();
  221.         return 0;
  222.     }
  223.     else
  224.     {
  225.         Sub3::Solve();
  226.         return 0;
  227.     }
  228.     return 0;
  229. }
  230.  
Success #stdin #stdout 0.01s 5620KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2g7sNc
language:
C++14 (gcc 8.3)
created:
1 day 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!