首页 > ACM题库 > HDU-杭电 > HDU 4558-剑侠情缘-动态规划-[解题报告]HOJ
2015
07-25

HDU 4558-剑侠情缘-动态规划-[解题报告]HOJ

剑侠情缘

问题描述 :

剑侠情缘是西山居工作室的扛鼎之作,从95年开始的单机版,到现在的第三代网络游戏,一直备受广大玩家喜爱。

有一天,由于你太过痴迷与喜爱这款游戏,于是,抱着你的一柄已经有点残破的长剑,开始了仗剑走天涯的生活。先不讲美人与美酒的故事,你要走的天涯,被我们有点无聊的简化为了一个二维矩阵。作为一个随性的大侠,你可以选择在任意一个点开始,然后在任意一个点结束你的旅途,在这个矩阵天涯里,你每一步只能向下或者向右移动一个格子,这段江湖旅途自然不能走出这个矩阵。

大侠也要面临窘迫的生活,是吧?你无法完全像游戏里面的人那样潇洒的来去如风,需要吃饭睡觉为自己补充能量,还需要不时修理你的剑,以免它残破的更厉害。在矩阵的每个点,有一个能量值,你可以选择为自己补充,也可以选择为你的爱剑补充。

经过一段时间的思考,你觉得这样比较平衡,在旅程的第一步,补充自己,下一步,也就是第二步补充剑,接着又补充自己,如此交替下去。一个必须要注意的问题是,你和剑能容纳的能量都是有上限的,超过这个上限后,计数器会溢出(不要问为什么,大家都是程序员)。具体来说,能量值只能维持在0-10范围之内,0为空,10为最佳。如果你当前的能量为10,补充了大小为1的能量,那么你的能量值就重新回到起点,变为0。

你意识到,其实最后能量值的大小无关紧要。你只希望你和你的剑能保持在统一水平,这样就可以依旧随心所欲的驾驭这把宝剑。而只要最后自己与剑的能量数值相等,这段与剑的情缘就足够牢固。你希望知道满足要求的情况下有多少种不同的选择方案,只要两种方案有任意一个不同的选择,就认为两种方案不同。

输入:

输入第一行为T,表示有T组测试数据。
每组数据以两个数组N,M开始,表示矩阵的大小。接着的N行每行包含一个长度为M的数字串Mi,表示矩阵内容。

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N, M <= 477
3. Mi只包含‘1’-‘9’的数字

输出:

输入第一行为T,表示有T组测试数据。
每组数据以两个数组N,M开始,表示矩阵的大小。接着的N行每行包含一个长度为M的数字串Mi,表示矩阵内容。

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N, M <= 477
3. Mi只包含‘1’-‘9’的数字

样例输入:

3
2 2
11
11
2 2
13
31
3 3
122
231
211

样例输出:

Case 1: 4
Case 2: 0
Case 3: 12

Hint
对第一组样例,四种方案是:(1,1)->(1,2), (1,1)->(2,1), (1,2)->(2,2), (2,1)->(2,2)。

题意:n×m (1<= N, M <=477) 的矩阵,a[i][j]表示第i行第j列的能量值,可以从任意点出发,任意点停止,但只能往右或往下走。

第一步给自己补充能量,第二步给剑补充能量,依次循环补充。能量值0~10,若当前为10,又补充了1的能量,则能量变成0。

要求离开的时候,人和剑的能量值相同,问有多少种不同的走法?结果对1 000 000 007取余。

分析:枚举人和剑的差值,人比剑多s,相当于人比剑少11-s。。。

设dp[x][y][i]表示在(x,y)位置,差值为i的方案数,

dp[x][y][i] = ( dp[x][y][i] + dp[x+1][y][j] ) % mod;

dp[x][y][i] = ( dp[x][y][i] + dp[x][y+1][j] ) % mod;

j为相邻格子的能量值,由于人和剑交替补充,对j取反为11-j,又当前格子本身有差值a[x][y],

所以i=11-j+a[x][y],  j=(11-i+a[x][y]) % 11;

 

 

int dx[] = {1,0,1,0};//up Right down Left
int dy[] = {0,1,0,-1};

const int M = 480, N = 11, mod = 1000000007;
char s[M];
int a[M][M], n, m, ans;
int dp[M][M][N];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    #endif

    int T; scanf("%d", &T);
    FOE(t, 1, T){
        ans = 0;
        memset(dp, 0, sizeof dp);
        scanf("%d%d", &n, &m);
        FOR(x, 0, n) {
            scanf("%s", s);
            FOR(y, 0, m) a[x][y] = s[y]-'0';
        }

        FOD(x, n-1, 0) {
            FOD(y, m-1, 0) {
                int v = a[x][y];
                FOR(i, 0, N) {
                    FOR(r, 0, 2) {
                        int xx=x+dx[r], yy=y+dy[r];
                        if(xx>=n || yy>=m) continue;

                        int temp = (11-i+v) % 11;
                        dp[x][y][i] = (dp[x][y][i] + dp[xx][yy][temp]) % mod;
                    }
                }
                dp[x][y][v]++;
                ans = ( ans + dp[x][y][0] ) % mod;
            }
        }
        printf("Case %d: %d\n", t, ans);
    }
    return 0;
}

 

参考:http://www.cnblogs.com/ts65213/archive/2013/05/26/3099978.html