P3473

金珂拉 · 2021-07-05 14:03:38 · 题解

题意

现在有一张 N \times M 的网格图，在这张图中有一些障碍物。

现在要求从左下角出发且方向向上，中间只能直行或右转，并且不能重复经过一个点，到达终点路径条数。

答案对k取模。

• 分析

• 正常dp

  首先，我们可以发现，既然只能右转，那么运动的路径就恰好是个螺旋状，而螺旋状的本质就是一个个不断缩小的矩阵

那么我们就可以发现，右转的过程实质上是在切割大矩形。如图，红线为路径，黑线为矩形。

令 f_{u,r,d,l,p} 表示在上为 u 下为 d 左为 l 右为 r 的矩阵上方向为 p (其中 0-3 分别表示上右下左）的边上运动时的方案数，那么小矩形就是大矩形的子问题，且满足加法原理。

那么，现在我们不考虑障碍物，就可以得到这样的方程。只要枚举在哪个点的地方转弯即可

若考虑障碍物，就有了这样的伪代码

for(int k;;)
f[u][r][d][l][0]+=f[k][r][d][l+1][0]*(路径上无障碍?1:0) 
for(int k;;)
f[u][r][d][l][1]+=f[u+1][k][d][l][1]*(路径上无障碍?1:0)
for(int k;;)
f[u][r][d][l][2]+=f[u][r-1][k][l][2]*(路径上无障碍?1:0)
for(int k;;)
f[u][r][d][l][3]+=f[u][r][d-1][k][3]*(路径上无障碍?1:0)

为方便起见，以下将(路径上无障碍?1:0)简记为 check(k) 。

• 考虑优化

但是我们发现，这样复杂度是 O(n^5) 的，显然会超时，必须把 k 的枚举优化掉

我们可以发现一个公式

以向上为例，有如下式子

没有了 k 的枚举，瞬间变成了 O(n^4) !

但是这样的空间依旧会超，所以我们可以使用滚动数组，然后发现每次枚举的两个子状态都满足行数和列数的和刚好比原状态少 1，所以可以考虑按行列数之和从小到大枚举。

• 注意事项

输入终点坐标时，先输入列再输入行，读入时应注意

• 代码

  /*
  最初的方程: 
  f[u][r][d][l][上]=∑f[k][r][d][l+1][右]*(路径上无障碍?1:0) 
  f[u][r][d][l][右]=∑f[u+1][k][d][l][下]*(路径上无障碍?1:0)
  f[u][r][d][l][下]=∑f[u][r-1][k][l][左]*(路径上无障碍?1:0)
  f[u][r][d][l][左]=∑f[u][r][d-1][k][上]*(路径上无障碍?1:0)
  这个显然是n^5的，时间会炸
  但是我们仔细一看就会发现 
  f[u][r][d][l][上]=∑f[k][r][d][l+1][右]*check(k)+f[u][r][d][l+1][右]*check(u)
  f[u][r][d][l][右]=∑f[u+1][k][d][l][下]*check(k)+f[u+1][r][d][l][下]*check(u)
  f[u][r][d][l][下]=∑f[u][r-1][k][l][左]*check(k)+f[u][r-1][d][l][左]*check(u)
  f[u][r][d][l][左]=∑f[u][r][d-1][k][上]*check(k)+f[u][r][d-1][l][上]*check(u)
  其中k的范围会缩小一步。
  也就是说，转移方程可以写成这样 
  f[u][r][d][l][上]=f[u][r][d][l+1][右]*(路径上无障碍?1:0)+f[u+1][r][d][l][上]
  f[u][r][d][l][右]=f[u+1][r][d][l][下]*(路径上无障碍?1:0) +f[u][r-1][d][l][右]
  f[u][r][d][l][下]=f[u][r-1][d][l][左]*(路径上无障碍?1:0)+f[u][r][d-1][l][下]
  f[u][r][d][l][左]=f[u][r][d-1][l][上]*(路径上无障碍?1:0)+f[u][r][d][l+1][左]
  但是发现空间不够用 
  不过，我们可以发现的是，每次转移，行数+列数恰好减少1,然后刚好转移也是一步步来的，可以滚动数组优化掉
  */              
  #include<bits/stdc++.h>
  using namespace std;
  int n,m,mod,y,x,s1[101][101],s2[101][101],dp[2][101][101][101][4];
  int main() {
  cin>>n>>m>>mod>>y>>x;
  for (int i=1;i<=n;++i)
  for (int j=1;j<=m;++j)
  {
      char c='.';
      while (c!='+' && c!='*') c=getchar();
      s1[i][j]=s1[i][j-1]+(c=='*'),
      s2[i][j]=s2[i-1][j]+(c=='*');
  }
  for (int s=2;s<=n+m;s++)
  for (int i=1;i<s;i++)
  for(int l=1;l<=y&&l<=m-s+i+1;l++)
  for(int u=1;u<=x&&u<=n-i+1;u++)
  {
  int d=u+i-1,r=l+s-i-1;
  if (d<x||r<y) continue;
  dp[s&1][u][l][d][0]=(dp[(s-1)&1][u+1][l][d][0]+(s2[d][l]==s2[u-1][l])*(dp[(s&1)^1][u][l+1][d][1]+(u==x&&l==y)))%mod;
  dp[s&1][u][l][d][1]=(dp[(s-1)&1][u][l][d][1]+(s1[u][r]==s1[u][l-1])*(dp[(s&1)^1][u+1][l][d][2]+(u==x&&r==y)))%mod;
  dp[s&1][u][l][d][2]=(dp[(s-1)&1][u][l][d-1][2]+(s2[d][r]==s2[u-1][r])*(dp[(s&1)^1][u][l][d][3]+(d==x&&r==y)))%mod;
  dp[s&1][u][l][d][3]=(dp[(s-1)&1][u][l+1][d][3]+(s1[d][r]==s1[d][l-1])*(dp[(s&1)^1][u][l][d-1][0]+(d==x&&l==y)))%mod;
  }
  cout<<dp[(n+m)&1][1][1][n][0];
  }