华为OD机试 2024E卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随着蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任何一方格或者游戏版图边界碰撞时，游戏结束。
下面让我们来完成贪吃蛇游戏的模拟。
给定一个 NM 的数组 arr，代表 NM 个方格组成的版图，贪吃蛇每次移动一个方格。
若 arr[i][j] == ‘H’，表示该方格为贪吃蛇的起始位置；
若 arr[i][j] == ‘F’，表示该方格为食物；
若 arr[i][j] == ‘E’，表示该方格为空格。
贪吃蛇初始长度为 1，初始移动方向为向右。
为给定一系列贪吃蛇的移动操作 K，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时蛇的长度。
贪吃蛇移动、吃食物和碰撞处理的细节见下图。
图1：截取了贪吃蛇移动的一个中间状态，H 表示蛇头，F 表示食物，数字为蛇的身体各节的编号，蛇为向左移动，此时蛇头和食物已经相邻。
图2：蛇头向左移动一格，蛇头和食物重叠，注意此时食物的格子成为了新的蛇头，第1节身体移动到蛇头位置，第2节身体移动到第1节身体位置，以此类推，最后添加第5节身体到原来第4节身体的位置。
图3：蛇头继续向右移动一格，身体的各节按上述规则移动，此时蛇头已经和边界相邻，但还未碰撞。
图4：蛇头继续向右移动一格，此时蛇头已经超过边界，发生碰撞，游戏结束。
图5和图6给出一个蛇头从身体碰撞的例子，蛇为向上移动。
图5时蛇头和第7节身体相邻，但还未碰撞；
图6蛇头向上移动一格，此时蛇头和第8节身体移动到了原来第7节身体的位置，发生碰撞，游戏结束。
二、输入描述
输入第一行为空格分隔的字母，代表贪吃蛇的移动操作。
字母取值为 U、D、L、R 和 G。
U、D、L、R 分别表示贪吃蛇向上、下、左、右移动，转向时贪吃蛇不移动，G 表示贪吃蛇按当前方向移动一格。
用例保证输入操作是正确的。
第二行为空格分隔的两个数，指定 N 和 M，为数组的行和列数。
余下 N 行每行是空格分隔的 M 个字符。字母取值为 H、F 和 E，H 表示贪吃蛇的起始位置，F 表示食物，E 表示该方格为空。
用例保证且只有一个 H 和 F，而 F 绝不会为 G。
三、输出描述
输出一个数字，为蛇的长度。
四、测试用例
测试用例1：
1、输入
D G G
3 3
F F F
F F H
E F E
2、输出
1
3、说明
地图表示为：
蛇头 H (Head)
食物 F (Food)
E 表示该方格为空
四个方向分别表示为：
向上 U (up)
向下 D (down)
向左 L (Left)
向右 R (Right)
测试用例2：
1、输入
R G G
3 3
F E E
H E F
E E E
2、输出
2
3、说明
五、解题思路
在这个问题中，队列是最合适的数据结构，用来存储蛇的身体部分。原因如下：
先进先出（FIFO）特性：蛇的身体是一个顺序结构，蛇头每次移动，新的头部位置加入，而尾部在蛇没有增长时会被移除。队列的先进先出性质刚好满足这个要求。
动态长度：蛇的长度可以根据是否吃到食物而变化，使用队列可以方便地进行头尾的动态增减操作。
- 初始化地图：我们首先读取地图的大小，并根据输入填充地图，标记蛇头、食物和空格的位置。
- 初始化蛇的状态：蛇最初的长度为1，只有蛇头。我们使用一个队列来存储蛇的身体部分。蛇头的位置记录在队列中。
- 移动模拟：
- 根据输入的移动命令调整蛇的移动方向（U, D, L, R分别代表上下左右，G代表按当前方向移动一格）。
- 每当蛇头移动时，检查是否越界或者撞到自身。如果发生上述情况，游戏立即结束，输出当前蛇的长度。
- 如果蛇头移动到食物所在位置，蛇的长度增加，不移除尾巴；否则蛇尾部分会被移除（队列的最前端出队）。
- 游戏结束条件：
- 如果蛇头碰到地图边界，或者与身体的其他部分相撞，游戏结束。
- 如果蛇完成所有移动，且没有碰到边界或撞到自身，则输出最终蛇的长度。
六、Python算法源码
from collections import deque
# 读取贪吃蛇的操作和地图
def snake_game(moves, N, M, grid):
# 定义四个方向 U, D, L, R 对应的移动
directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
# 初始化蛇头位置和队列
snake = deque() # 使用 deque 模拟队列
headX, headY = 0, 0 # 初始化蛇头位置
# 找到蛇头位置
for i in range(N):
for j in range(M):
if grid[i][j] == 'H':
headX, headY = i, j
snake.append((i, j)) # 将初始蛇头加入队列
snake_length = 1 # 蛇的初始长度
direction = 'R' # 初始方向为右
# 执行每一个操作
for move in moves:
if move in "UDLR":
direction = move # 改变方向
elif move == 'G': # 执行移动
# 根据当前方向获取蛇头新的位置
dx, dy = directions[direction]
newX, newY = headX + dx, headY + dy
# 检查是否越界
if newX < 0 or newX >= N or newY < 0 or newY >= M:
return snake_length # 游戏结束，输出蛇长度
# 检查是否撞到自己
if (newX, newY) in snake:
return snake_length # 撞到自己，游戏结束
# 移动蛇头
if grid[newX][newY] == 'F': # 吃到食物
snake_length += 1 # 增加长度
else:
snake.popleft() # 没有吃到食物，移除尾巴
snake.append((newX, newY)) # 加入新的头部位置
headX, headY = newX, newY # 更新蛇头位置
return snake_length # 返回最终蛇的长度
# 测试用例1
moves = ['D', 'G', 'G']
N, M = 3, 3
grid = [['F', 'F', 'F'],
['F', 'F', 'H'],
['E', 'F', 'E']]
print(snake_game(moves, N, M, grid)) # 应该输出 1
七、JavaScript算法源码
function snakeGame(moves, N, M, grid) {
let directions = { 'U': [-1, 0], 'D': [1, 0], 'L': [0, -1], 'R': [0, 1] };
let snake = []; // 用数组模拟队列
let headX = 0, headY = 0;
let snakeLength = 1;
let direction = 'R'; // 初始方向向右
// 找到蛇头位置
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (grid[i][j] === 'H') {
headX = i;
headY = j;
snake.push([i, j]);
}
}
}
// 处理每个操作
for (let move of moves) {
if (move in directions) {
direction = move; // 更改方向
} else if (move === 'G') { // 按当前方向移动
let [dx, dy] = directions[direction];
let newX = headX + dx, newY = headY + dy;
// 检查是否越界
if (newX < 0 || newX >= N || newY < 0 || newY >= M) {
return snakeLength;
}
// 检查是否撞到自己
if (snake.some(([x, y]) => x === newX && y === newY)) {
return snakeLength;
}
// 移动蛇头
if (grid[newX][newY] === 'F') {
snakeLength++;
} else {
snake.shift(); // 没有吃到食物，移除尾巴
}
snake.push([newX, newY]);
headX = newX;
headY = newY;
}
}
return snakeLength;
}
// 测试用例
let moves = ['D', 'G', 'G'];
let N = 3, M = 3;
let grid = [['F', 'F', 'F'],
['F', 'F', 'H'],
['E', 'F', 'E']];
console.log(snakeGame(moves, N, M, grid)); // 应该输出 1
八、C算法源码
#include <stdio.h>
#include <stdbool.h>
#define MAX 50
// 用于存储方向的数组
int dx[4] = {-1, 1, 0, 0}; // 上下左右方向
int dy[4] = {0, 0, -1, 1};
// 定义结构体用于存储蛇的坐标
typedef struct {
int x, y;
} Point;
int snake_game(char moves[], int move_count, int N, int M, char grid[MAX][MAX]) {
Point snake[MAX * MAX]; // 用于存储蛇的身体
int snake_length = 1;
int headX = 0, headY = 0;
char direction = 'R'; // 初始方向为右
// 找到蛇头位置
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == 'H') {
headX = i;
headY = j;
snake[0].x = i;
snake[0].y = j;
}
}
}
// 遍历操作
for (int i = 0; i < move_count; i++) {
char move = moves[i];
// 更改方向
if (move == 'U') direction = 'U';
else if (move == 'D') direction = 'D';
else if (move == 'L') direction = 'L';
else if (move == 'R') direction = 'R';
else if (move == 'G') { // 移动
int dir_index;
if (direction == 'U') dir_index = 0;
else if (direction == 'D') dir_index = 1;
else if (direction == 'L') dir_index = 2;
else if (direction == 'R') dir_index = 3;
int newX = headX + dx[dir_index];
int newY = headY + dy[dir_index];
// 检查是否越界
if (newX < 0 || newX >= N || newY < 0 || newY >= M) {
return snake_length;
}
// 检查是否撞到自己
for (int j = 0; j < snake_length; j++) {
if (snake[j].x == newX && snake[j].y == newY) {
return snake_length;
}
}
// 移动蛇头
if (grid[newX][newY] == 'F') {
snake_length++; // 吃到食物，长度增加
} else {
// 没吃到食物，移除尾巴
for (int j = 1; j < snake_length; j++) {
snake[j - 1] = snake[j];
}
snake_length--;
}
// 添加新头部
snake[snake_length - 1].x = newX;
snake[snake_length - 1].y = newY;
headX = newX;
headY = newY;
}
}
return snake_length;
}
int main() {
char moves[] = {'D', 'G', 'G'};
int N = 3, M = 3;
char grid[MAX][MAX] = {
{'F', 'F', 'F'},
{'F', 'F', 'H'},
{'E', 'F', 'E'}
};
int move_count = 3;
int result = snake_game(moves, move_count, N, M, grid);
printf("%d\n", result); // 应该输出 1
return 0;
}
九、C++算法源码
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
struct Point {
int x, y;
};
int snake_game(vector<char>& moves, int N, int M, vector<vector<char>>& grid) {
deque<Point> snake; // 用 deque 作为队列
int headX = 0, headY = 0;
int snake_length = 1;
char direction = 'R'; // 初始方向为右
// 定义方向
vector<int> dx = {-1, 1, 0, 0};
vector<int> dy = {0, 0, -1, 1};
vector<char> dir_map = {'U', 'D', 'L', 'R'};
// 找到蛇头位置
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (grid[i][j] == 'H') {
headX = i;
headY = j;
snake.push_back({i, j});
}
}
}
// 处理每个操作
for (char move : moves) {
if (move == 'U' || move == 'D' || move == 'L' || move == 'R') {
direction = move; // 改变方向
} else if (move == 'G') {
// 按当前方向移动
int dir_idx = find(dir_map.begin(), dir_map.end(), direction) - dir_map.begin();
int newX = headX + dx[dir_idx];
int newY = headY + dy[dir_idx];
// 检查是否越界
if (newX < 0 || newX >= N || newY < 0 || newY >= M) {
return snake_length;
}
// 检查是否撞到自己
for (auto& p : snake) {
if (p.x == newX && p.y == newY) {
return snake_length;
}
}
// 移动蛇头
if (grid[newX][newY] == 'F') {
snake_length++; // 吃到食物
} else {
snake.pop_front(); // 没有吃到食物，移除尾巴
}
snake.push_back({newX, newY});
headX = newX;
headY = newY;
}
}
return snake_length;
}
int main() {
vector<char> moves = {'D', 'G', 'G'};
int N = 3, M = 3;
vector<vector<char>> grid = {
{'F', 'F', 'F'},
{'F', 'F', 'H'},
{'E', 'F', 'E'}
};
cout << snake_game(moves, N, M, grid) << endl; // 应该输出 1
return 0;
}
🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）
🏆本文收录于，华为OD机试真题（Python/JS/C/C++）
刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。
