题目描述
贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。
下面让我们来完成贪吃蛇游戏的模拟。
给定一个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节身体的位置，发生碰撞，游戏结束。
输入描述
输入第一行为空格分隔的字母，代表贪吃蛇的移动操作。
字母取值为U、D、L、R和G，
U、D、L、R分别表示贪吃蛇往上、下、左、右和转向，转向时贪吃蛇不移动 ，G表示贪吃蛇按当前的方向移动一格。
用例保证输入的操作正确。
第二行为空格分隔的两个数，指定N和M，为数组的行和列数。
余下N行每行是空格分隔的M个字母。字母取值为H、F和E，H表示贪吃蛇的起始位置，F表示食物，E表示该方格为空。
用例保证有且只有一个H，而F和E会有多个。
输出描述
输出一个数字，为蛇的长度。
用例
| 输入 | D G G 3 3 F F F F F H E F E |
| 输出 | 1 |
| 说明 |
地图表示为：
四个方向分别表示为：
|
题目解析
纯逻辑题。
本题难点在于当贪吃蛇移动后，更新贪吃蛇的位置，以及矩阵各坐标的信息的逻辑。
首先，我使用一个数组snake来维护贪吃蛇的位置，蛇头就是snake[0]。
当贪吃蛇移动时，如果蛇头去往的位置是空地，即matrix[i][j] = 'E'的话，则
snake.unshift([i,j])
let [aI, aJ] = snake.pop() // 由于去往的是空地，因此贪吃蛇不会生长，所以蛇尾的位置要pop出去
matrix[aI][aJ] = 'E' // 并且要更新pop出去的位置为空地
matrix[i][j] = 'H' // 而蛇头达到的新位置要更新为蛇头位置H当贪吃蛇移动时，如果蛇头去往的位置是食物，即matrix[i][j] = 'F'的话，则
snake.unshift([i,j])
matrix[i][j] = 'H' // 更新蛇头位置当贪吃蛇移动时，如果蛇头去往的位置是自己的身体，即matrix[i][j] = 'H'，
注意我这里并不需要根据‘H’来判断移动中蛇头的位置，而是总是用snake[0]作为蛇头，因此matrix[i][j] = 'H'可以直接用于标记贪吃蛇身体，来区别F、E。
则，此时游戏结束，输出snake.length
另外，当贪吃蛇移动的位置越界了，游戏也结束，输出snake.length
自测用例
D G L G G U G G R G G D G L G
3 3
F F F
F F H
E F E
最终贪吃蛇的长度为7
D G L G U G R G U G L G D G
3 3
F F F
F F H
E F E
最终贪吃蛇的长度为5
JavaScript算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
const operates = (await readline()).split(" ");
const [n, m] = (await readline()).split(" ").map(Number);
const matrix = [];
for (let i = 0; i < n; i++) {
matrix.push((await readline()).split(" "));
}
const snake = [];
const offset = [0, -1]; // 蛇头移动初始向左
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if ("H" == matrix[i][j]) snake.push(new Pos(i, j)); // 找到初始蛇头位置，并使用snake[0]来维护蛇头位置
}
}
for (let op of operates) {
switch (op) {
case "U":
offset[0] = -1;
offset[1] = 0;
break;
case "D":
offset[0] = 1;
offset[1] = 0;
break;
case "L":
offset[0] = 0;
offset[1] = -1;
break;
case "R":
offset[0] = 0;
offset[1] = 1;
break;
case "G":
const head = snake[0];
const head_next = new Pos(head.x + offset[0], head.y + offset[1]);
if (
head_next.x < 0 ||
head_next.x >= n ||
head_next.y < 0 ||
head_next.y >= m
) {
return console.log(snake.length);
}
const tail = snake.at(-1);
switch (matrix[head_next.x][head_next.y]) {
case "E":
// 如果蛇头去的地方是空地，则:
// 蛇身的每个位置都递进为前面一个位置，蛇尾巴位置恢复为空地
matrix[tail.x][tail.y] = "E";
snake.pop();
// 蛇头进入新位置
matrix[head_next.x][head_next.y] = "H";
snake.unshift(head_next);
break;
case "F":
// 如果蛇头去的地方是食物，则蛇身长度增加一，相当于蛇身各部分位置不变，蛇头变到当前去的位置
matrix[head_next.x][head_next.y] = "H";
snake.unshift(head_next);
break;
case "H":
if (head_next.eq(tail)) {
// 如果蛇头去的地方是蛇尾，则由于递进关系，蛇头是吃不到蛇尾的
snake.unshift(snake.pop());
} else {
// 如果蛇头去的地方是蛇身，则会吃到自己
return console.log(snake.length);
}
break;
}
break;
}
}
console.log(snake.length);
})();
class Pos {
constructor(x, y) {
this.x = x;
this.y = y;
}
eq(pos) {
return this.x == pos.x && this.y == pos.y;
}
}
Java算法源码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
// 坐标类
static class Pos {
int x;
int y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Pos pos) {
return this.x == pos.x && this.y == pos.y;
}
}
static String[] operates;
static String[][] matrix;
static int n;
static int m;
static LinkedList<Pos> snake = new LinkedList<>();
static int[] offset = new int[] {0, -1}; // 蛇头移动初始向左
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
operates = sc.nextLine().split(" ");
int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
n = tmp[0];
m = tmp[1];
matrix = new String[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
matrix[i][j] = sc.next();
if ("H".equals(matrix[i][j])) {
snake.addLast(new Pos(i, j)); // 找到初始蛇头位置，并使用snake[0]来维护蛇头位置
}
}
}
System.out.println(getResult());
}
public static int getResult() {
for (String operate : operates) {
switch (operate) {
case "U":
offset[0] = -1;
offset[1] = 0;
break;
case "D":
offset[0] = 1;
offset[1] = 0;
break;
case "L":
offset[0] = 0;
offset[1] = -1;
break;
case "R":
offset[0] = 0;
offset[1] = 1;
break;
case "G":
Pos head = snake.getFirst();
Pos head_next = new Pos(head.x + offset[0], head.y + offset[1]);
if (head_next.x < 0 || head_next.x >= n || head_next.y < 0 || head_next.y >= m) {
return snake.size();
}
Pos tail = snake.getLast();
switch (matrix[head_next.x][head_next.y]) {
case "E":
// 如果蛇头去的地方是空地，则:
// 蛇身的每个位置都递进为前面一个位置，蛇尾巴位置恢复为空地
matrix[tail.x][tail.y] = "E";
snake.removeLast();
// 蛇头进入新位置
matrix[head_next.x][head_next.y] = "H";
snake.addFirst(head_next);
break;
case "F":
// 如果蛇头去的地方是食物，则蛇身长度增加一，相当于蛇身各部分位置不变，蛇头变到当前去的位置
matrix[head_next.x][head_next.y] = "H";
snake.addFirst(head_next);
break;
case "H":
if (head_next.equals(tail)) {
// 如果蛇头去的地方是蛇尾，则由于递进关系，蛇头是吃不到蛇尾的
snake.addFirst(snake.removeLast());
} else {
// 如果蛇头去的地方是蛇身，则会吃到自己
return snake.size();
}
break;
}
break;
}
}
return snake.size();
}
}
Python算法源码
# 输入获取
operates = input().split()
n, m = map(int, input().split())
matrix = [input().split() for _ in range(n)]
# 记录蛇各个部分位置
snake = []
# 蛇头移动初始向左 [行偏移量，列偏移量]，向左即列位置-1
offset = [0, -1]
# 坐标类
class Pos:
def __init__(self, x, y):
self.x = x
self.y = y
def __eq__(self, other):
return self.x == other.x and self.y == other.y
# 算法入口
def getResult():
# 找到初始蛇头位置，并使用snake[0]来维护蛇头位置
for i in range(n):
for j in range(m):
if "H" == matrix[i][j]:
snake.append(Pos(i, j))
for op in operates:
if op == "U":
offset[0] = -1
offset[1] = 0
elif op == "D":
offset[0] = 1
offset[1] = 0
elif op == "L":
offset[0] = 0
offset[1] = -1
elif op == "R":
offset[0] = 0
offset[1] = 1
elif op == "G":
head = snake[0]
head_next = Pos(head.x + offset[0], head.y + offset[1])
if head_next.x < 0 or head_next.x >= n or head_next.y < 0 or head_next.y >= m:
return len(snake)
tail = snake[-1]
cell = matrix[head_next.x][head_next.y]
if cell == "E":
# 如果蛇头去的地方是空地，则:
# 蛇身的每个位置都递进为前面一个位置，蛇尾巴位置恢复为空地
matrix[tail.x][tail.y] = "E"
snake.pop()
# 蛇头进入新位置
matrix[head_next.x][head_next.y] = "H"
snake.insert(0, head_next)
elif cell == "F":
# 如果蛇头去的地方是食物，则蛇身长度增加一，相当于蛇身各部分位置不变，蛇头变到当前去的位置
matrix[head_next.x][head_next.y] = "H"
snake.insert(0, head_next)
elif cell == "H":
# 如果蛇头去的地方是蛇尾，则由于递进关系，蛇头是吃不到蛇尾的
if head_next == tail:
snake.insert(0, snake.pop())
else:
# 如果蛇头去的地方是蛇身，则会吃到自己
return len(snake)
return len(snake)
# 算法调用
print(getResult())
免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0