POI2008 The Great Escape

POI
dp

POI2008 The Great Escape

题目大意：

给出一个$n \times m$的地图，计算从(n,1)走到(y,x)的路径条数。答案对k取模，走过的点不能再走，转弯只能向右转。（有的格子可能存在障碍，不能走）

($ n,m \le 100$)

题解：

借鉴了Sengxian的题解

戳这儿

模拟数据，我们不难发现，路径都是绕着圈圈到达的。

由于走过的点不能再走，并且转弯只能向右转，因而，路径的圈一定是越转越小的。

为了方便，我们计算从(y,x)走到(n,1)的方案数，转弯只能向左转。这样圈一定是越转越大的。

定义dp[x1][y1][x2][y2][0~4]表示从(y,x)出发，所走的路径上界为x1，下界为x2，左界为y1，右界为y2，终点分别为(x1,y2)、(x2,y2)、(x2,y1)、(x1,y1)的可行路径数。

看右上角的点:

  • dp[x1][y1][x2][y2][0] $ \leftarrow $ dp[x1][y1][x2][y2-1][1] （从右下角的点向左转）
  • dp[x1][y1][x2][y2][0] $ \leftarrow $ dp[x1+1][y1][x2][y2][0] （从右上角的点直接走）

同理可以得到其余三个角的转移方程：

  • dp[x1][y1][x2][y2][1] $ \leftarrow $ dp[x1][y1][x2-1][y2][2] + dp[x1][y1][x2][y2-1][1]
  • dp[x1][y1][x2][y2][2] $ \leftarrow $ dp[x1][y1+1][x2][y2][3] + dp[x1][y1][x2-1][y2][2]
  • dp[x1][y1][x2][y2][3] $ \leftarrow $ dp[x1+1][y1][x2][y2][0] + dp[x1][y1+1][x2][y2][3]

设立初值比较麻烦，Sengxian的方法是将起点 (y,x)需要的状态设置为 1（哪怕这个状态不合格），这样比较方便。

这样一来，时间复杂度为$O(n^4)$ ，空间上可以用滚动数组来优化，复杂度为$O(n^3)$。

PS. 状态的定义比较奇妙，蛮神的一道dp题。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=105;
int n,m,mod,x,y,ans;
char str[N];
int lin[N][N],row[N][N],dp[2][N][N][N][4];
void Mod(int&a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&mod,&y,&x);   
    for(int i=1;i<=n;i++){
        scanf("%s",str+1);
        for(int j=1;j<=m;j++){
            lin[i][j]=lin[i][j-1]+(str[j]=='+');
            row[j][i]=row[j][i-1]+(str[j]=='+');
        }
    }
    bool cur=0;
    dp[cur][y][x][y-1][1]=1;
    dp[cur][y][x-1][y][2]=1;
    dp[cur][y+1][x][y][3]=1;
    dp[cur^1][y][x][y][0]=1;
    for(int x1=x;x1>=1;x1--,cur^=1){
        if(x1!=x)memset(dp[cur],0,sizeof(dp[cur]));
        for(int y1=y;y1>=1;y1--){
            for(int x2=x;x2<=n;x2++){
                for(int y2=y;y2<=m;y2++){
                    if(row[y2][x2]-row[y2][x1-1]==x2-x1+1){
                        dp[cur][y1][x2][y2][0]=dp[cur][y1][x2][y2-1][1];
                        if(x1<x2)Mod(dp[cur][y1][x2][y2][0],dp[cur^1][y1][x2][y2][0]);
                    }
                    if(lin[x2][y2]-lin[x2][y1-1]==y2-y1+1){
                        dp[cur][y1][x2][y2][1]=dp[cur][y1][x2-1][y2][2];
                        if(y1<y2)Mod(dp[cur][y1][x2][y2][1],dp[cur][y1][x2][y2-1][1]);
                    }
                    if(row[y1][x2]-row[y1][x1-1]==x2-x1+1){
                        dp[cur][y1][x2][y2][2]=dp[cur][y1+1][x2][y2][3];
                        if(x1<x2)Mod(dp[cur][y1][x2][y2][2],dp[cur][y1][x2-1][y2][2]);
                    }
                    if(lin[x1][y2]-lin[x1][y1-1]==y2-y1+1){
                        dp[cur][y1][x2][y2][3]=dp[cur^1][y1][x2][y2][0];
                        if(y1<y2)Mod(dp[cur][y1][x2][y2][3],dp[cur][y1+1][x2][y2][3]);
                    }
                    if(x2==n&&y1==1)Mod(ans,dp[cur][y1][x2][y2][2]);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}
分享到 评论