ECNUOJ 2855 贪吃蛇

贪吃蛇

Time Limit:1000MS Memory Limit:65536KB
Total Submit:480 Accepted:109

Description 

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

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

请你输出T时刻蛇的生命力。方向对应关系为：上(0)、右(1)、下(2)、左(3).

Input 

每个文件一个测试数据：

数据的第一行三个整数H，W，T 。( 2 <= H、W<=100 ，0<=T<=1000 )

接下来H行，每行W个字符，其中‘.’表示可行走的空地，‘0’-‘9’表示价值不同的蘑菇，相应的价值分别为0-9

Output 

对于每组数据，输出一个值，表示T时刻后（含T时刻）蛇的生命力

Sample Input 

2 3 4

145

1..

Sample 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

(请多体会这个"方向"的含义)

Source

解题：我就不吐槽这题，题意真尼玛晦涩难懂

#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
char table[maxn][maxn];
int H,W,T,f[1001] = {0,1};
const int dir[4][2] = {-1,0,0,1,1,0,0,-1};
bool isIn(int x,int y){
    return x < H && x >= 0 && y >= 0 && y < W;
}
int solve(){
    int life = isdigit(table[0][0])?table[0][0] - '0':0,nowdir = 0,time = 0;
    int x = 0,y = 0;
    while(time < T){
        int nx = x + dir[nowdir = f[time]][0];
        int ny = y + dir[f[time]][1];
        while(!isIn(nx,ny)){
            nowdir++;
            nx = x + dir[nowdir%4][0];
            ny = y + dir[nowdir%4][1];
        }
        x = nx;
        y = ny;
        time++;
        if(isdigit(table[x][y])) life += table[x][y] - '0';
    }
    return life;
}
int main(){
    for(int i = 2; i < 1001; ++i)
        f[i] = (f[i-1] + f[i-2])%4;
    while(~scanf("%d%d%d",&H,&W,&T)){
        for(int i = 0; i < H; ++i)
            scanf("%s",table[i]);
        printf("%d
",solve());
    }
    return 0;
}