剑侠情缘

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

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

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

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

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

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

[Technical Specification]

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

Output
对每组数据,先输出为第几组数据,然后输出满足要求的方案种数。由于可能很大,输出对1 000 000 007取余后的结果。

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

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题