23. 贪吃蛇

贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。

下面让我们来完成贪吃蛇游戏的模拟。

给定一个N*M的数组arr，代表N*M个方格组成的版图，贪吃蛇每次移动一个方格.

若arr[i][j]==“H’，表示该方格为贪吃蛇的起始位置:

若arr[i][j]==“F’，表示该方格为食物

若arr[i][j]==“E”，表示该方格为空格.

贪吃蛇初始长度为1，初始移动方向为向左

为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时蛇的长度。

贪吃蛇移动、吃食物和碰撞处理的细节见下面图示

图一
 

图二
 

图三
 

图四
 

图五
 

图六

图 1:截取了贪吃蛇移动的一个中间状态，H表示蛇头，F表示食物，数字为蛇身体各节的 编号，蛇为向左移动，此时蛇头和食物已经相邻。

图 2:蛇头向左移动一格，蛇头和食物重叠，注意此时食物的格子成为了新的蛇头，第 1节 身体移动到蛇头位置，第 2节身体移动到第 1节身体位置，以此类推，最后添加第 4节升 起到原来第 3节身体的位置。

图 3:蛇头继续向左移动一格，身体的各节按上述规则移动，此时蛇头已经和边界相邻，但 还未碰撞。

图 4:蛇头继续向左移动一格，此时蛇头已经超过边界，发生碰撞，游戏结束。

图 5和图 6给出一个蛇头和身体碰撞的例子，蛇为向上移动。图 5时蛇头和第 7节身体相 邻，但还未碰撞;图 6蛇头向上移动一格，此时蛇头和第 8节身体都移动到了原来第 7节 身体的位置，发生碰撞，游戏结束。

输入描述: 输入第 1行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为 U、D、L、R、G，其中U、D、L、R分别表示贪吃蛇往上、下、左、右转向，转向时贪吃蛇不移动，G表示贪吃蛇按 当前的方向移动一格。用例保证输入的操作正确。
第 2行为空格分隔的两个数，指定为 N和 M，为数组的行和列数。余下 N行每行是空格分 隔的 M个字母。字母取值为 H、F和 E，H表示贪吃蛇的起始位置，F表示食物，E表示该 方格为空。用例保证有且只有一个 H，而 F和 E会有多个。
输出描述:
输出一个数字为蛇的长度。
示 例:
输入
DGG
3 3
FFF
FFH
EFE
输出
1

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.贪吃蛇是一个经典游戏，蛇的身体由若干方块连接而成

2.身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。

3.蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。

4.模拟贪吃蛇游戏：给定一个N*M的数组arr，代表N*M个方格组成的版图，贪吃蛇每次移动一格方格。若arr[i][j]=='H'，表示该方格为贪吃蛇的起始位置，若arr[i][j]=='F'，表示该方格为食物，若arr[i][j]=='E'，表示该方格为空格

5.贪吃蛇初始长度为1，初始移动方向为向左。输入为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时贪吃蛇的长度。

6.输入描述：输入第一行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为U、D、L、R、G，其中U、D、L、R分别表示贪吃蛇往上、下、左、右转向，转向时贪吃蛇不移动，G表示贪吃蛇按当前的方向移动一格。用例保证输入的操作正确。

第二行为空格分隔的两个数，指定为N和M，为数组的行和列数。余下N行每行是空格分隔的M个字母。字母取值为H、F和E，H表示贪吃蛇的起始位置，F表示食物，E表示该方格为空。用例保证有且只有一个H，而F和E会有多个。

7.输出描述：输出一个数字为蛇的长度。

二、解题思路

1.首先引入标准输入输出库

#include <stdio.h>

2.开始主程序

int main()

3.定义变量读取数据，首先读取第一行的命令

char str[1000];

fgets(str, sizeof(str), stdin);

str[strcspn(str,"\n")] = '\0';

4.然后读取第二行的N和M， int N, M;

scanf("%d %d", &N, &M);

5.然后读取余下N行，每行M个字母

char graph[N][M];

for(int i = 0; i < N; i++) {

for(int j = 0; j < M; j++) {

scanf("%c", &graph[i][j]);

}

}

6.然后开始根据命令控制贪吃蛇

我们需要设置贪吃蛇的方向，int di = 0;

di为0代表向左走（默认），1表示向右走，2表示向上走，3表示向下走

还需要设置贪吃蛇的长度，int long = 1；

还需要定义贪吃蛇身体每一个部分的坐标，int body[N * M][2];

读取数组的时候如果读取到字母为H的坐标i,j

int body[0][0] = i; int body[0][1] = j;

7.注意转向的时候贪吃蛇不移动（只有命令是G的时候才移动）

当我们收到的命令是UDLR的时候我们的di的值分别变成2301

8.当我们收到的命令是G的时候我们有几种情况，

首先我们确定头部的位置，如果我们向左走，我们前方的坐标是x = body[0][0],y = body[0][1] - 1

如果向右走我们前方的坐标是x = body[0][0],y = body[0][1] + 1

如果向上走我们前方的坐标是x = body[0][0] - 1, y = body[0][1]

如果向下走我们前方的坐标是x = body[0][0] + 1， y = body[0][1]

我们需要判断这两个数字x,y在graph中的位置，如果x或者y< 0了或者x>=M了y>=N了那么我们可以返回蛇的长度（因为游戏结束）

然后我们还需要判断如果long > 1的时候我们需要遍历身体的左边，如果身体有坐标在x,y那么我们游戏结束（因为触碰身体游戏结束）返回蛇的长度

否则如果graph[x][y]是F，我们的头部变成F的位置同时我们long++；

如果是E，我们需要将身体每一个部分移动，（可以从后向前移动，每个部分的左边变成前一个部分原来的坐标）最后将头部坐标设置成x,y

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <string.h>

// 检查坐标是否在游戏版图内
int isInBoard(int x, int y, int N, int M) {
    return (x >= 0 && x < N && y >= 0 && y < M);
}

int main() {
    // 1. 读取操作命令
    char str[1000];
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = '\0';

    // 2. 读取游戏版图的行数和列数
    int N, M;
    scanf("%d %d", &N, &M);
    //printf("N is %d , M is %d\n", N, M);
    // 3. 读取游戏版图
    char graph[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf(" %c", &graph[i][j]);  // 注意这里需要添加一个空格，避免读取换行符
            //printf("position %d %d is %c\n", i, j , graph[i][j]);
        }
        // printf("\n");
    }

    // 4. 初始化贪吃蛇相关信息
    int di = 0;  // 初始方向向左
    int length = 1;
    int body[N * M][2];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (graph[i][j] == 'H') {
                body[0][0] = i;
                body[0][1] = j;
                //printf("found heard at position %d %d\n", i , j);
                break;
            }
        }
    }

    // 5. 处理操作命令
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == 'U') {
            di = 2;
        } else if (str[i] == 'D') {
            di = 3;
        } else if (str[i] == 'L') {
            di = 0;
        } else if (str[i] == 'R') {
            di = 1;
        } else if (str[i] == 'G') {
            // printf("command G\n");
            int x = body[0][0];
            int y = body[0][1];
            // 根据当前方向计算下一步头部位置
            if (di == 0) {
                y--;
            } else if (di == 1) {
                y++;
            } else if (di == 2) {
                x--;
            } else if (di == 3) {
                x++;
            }

            // 检查是否撞墙或撞到身体
            if (!isInBoard(x, y, N, M) || graph[x][y] == 'B') {
                printf("%d\n",length);
                return 0;
            }

            // 处理吃到食物或移动到空格的情况
            if (graph[x][y] == 'F') {
                // printf("graph[%d][%d]meet food\n",x,y);
                length++;
                graph[x][y] = 'H';
                graph[body[0][0]][body[0][1]] = 'B';
                for(int i = length - 1; i > 0; i--) {
                    body[i][0] = body[i - 1][0];
                    body[i][1] = body[i - 1][1];
                }
            } else if (graph[x][y] == 'E') {
                // 移动身体
                graph[body[0][0]][body[0][1]] = 'B';
                graph[body[length - 1][0]][body[length - 1][1]] = 'E';
                graph[x][y] = 'H';
                for (int i = length - 1; i > 0; i--) {
                    body[i][0] = body[i - 1][0];
                    body[i][1] = body[i - 1][1];
                }
            }

            // 更新头部位置
            body[0][0] = x;
            body[0][1] = y;
        }
    }

    // 6. 输出最终蛇的长度
    printf("%d\n", length);

    return 0;
}