2855. 贪吃蛇

单点时限: 2.0 sec

内存限制: 256 MB

相信很多人都玩过这个游戏,当然这个题目不是叫你写一个贪吃蛇游戏,而是很简单的模拟而已,为了简化规则,我们把游戏抽象为:

在 H×W 的格点上有一条小小的长度为 1 的蛇,这条蛇每次只能向上下左右四个方向移动一个单位距离。在某些格点上有营养价值不同的蘑菇,当蛇移动到含有蘑菇的点的时候,其生命力会增加相应的值。在每个时间点,其选择的方向是由函数 Fn % 4 决定的,其中 F0 = 0,F1 = 1,Fn = Fn - 1 + Fn – 2 。如果蛇选择的方向会立即撞到墙,它会沿着该方向的顺时针选择第一个不会撞到墙的方向作为该时刻的方向。初始时刻是 0 时刻,蛇在左上角,初始生命力为 0,某个点上的蘑菇在吃掉后会立刻长出来。最外一圈是墙,没有给出来。 请你输出 T 时刻蛇的生命力。方向对应关系为:上 (0)、右 (1)、下 (2)、左 (3).

输入格式

每个文件一个测试数据:

数据的第一行三个整数 H,W,T 。( 2 <= H、W<=100 ,0<=T<=1000 ) 接下来 H 行,每行 W 个字符,其中 ‘.’ 表示可行走的空地,‘0’-‘9’ 表示价值不同的蘑菇,相应的价值分别为 0-9

输出格式

对于每组数据,输出一个值,表示 T 时刻后(含 T 时刻)蛇的生命力

样例

Input
2 3 4
145
1..
Output
10
Hint:
0时刻蛇在(0,0) , 方向0,但是会出界,顺时针选择第一个不出界的方向1,生命力1
1时刻蛇在(0,1) , 方向1,生命力5
2时刻蛇在(0,2), 方向1,会出界,选择方向2,生命力10
3时刻蛇在(1,2), 方向2,会出界,选择方向3,生命力10
4时刻蛇在(1,1), 方向3,生命力10
(请多体会这个"方向"的含义)

125 人解决,210 人已尝试。

184 份提交通过,共有 863 份提交。

4.1 EMB 奖励。

创建: 13 年,8 月前.

修改: 7 年,1 月前.

最后提交: 5 月,2 周前.

来源: N/A

题目标签