​LeetCode刷题实战353:贪吃蛇

今天和大家聊的问题叫做 贪吃蛇,我们先来看题面:
https://leetcode-cn.com/problems/design-snake-game/
Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.
The snake is initially positioned at the top left corner (0,0) with length = 1 unit.
You are given a list of food's positions in row-column order. When a snake eats the food, its length and the game's score both increase by 1.
Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.
When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.
请你设计一个 贪吃蛇游戏,该游戏将会在一个 屏幕尺寸 = 宽度 x 高度 的屏幕上运行。如果你不熟悉这个游戏,可以 点击这里 在线试玩。
起初时,蛇在左上角的 (0, 0) 位置,身体长度为 1 个单位。
你将会被给出一个 (行, 列) 形式的食物位置序列。当蛇吃到食物时,身子的长度会增加 1 个单位,得分也会 +1。
食物不会同时出现,会按列表的顺序逐一显示在屏幕上。比方讲,第一个食物被蛇吃掉后,第二个食物才会出现。
当一个食物在屏幕上出现时,它被保证不能出现在被蛇身体占据的格子里。
对于每个 move() 操作,你需要返回当前得分或 -1(表示蛇与自己身体或墙相撞,意味游戏结束)。

示例

示例:

给定 width = 3, height = 2, 食物序列为 food = [[1,2],[0,1]]。

Snake snake = new Snake(width, height, food);

初始时,蛇的位置在 (0,0) 且第一个食物在 (1,2)。

|S| | |
| | |F|

snake.move('R'); -> 函数返回 0

| |S| |
| | |F|

snake.move('D'); -> 函数返回 0

| | | |
| |S|F|

snake.move('R'); -> 函数返回 1 
(蛇吃掉了第一个食物,同时第二个食物出现在位置 (0,1))

| |F| |
| |S|S|

snake.move('U'); -> 函数返回 1

| |F|S|
| | |S|

snake.move('L'); -> 函数返回 2 (蛇吃掉了第二个食物)

| |S|S|
| | |S|

snake.move('U'); -> 函数返回 -1 (蛇与边界相撞,游戏结束


解题

https://blog.csdn.net/zshouyi/article/details/73335535
写一个贪吃蛇的程序,每吃到一个food,长度加一,撞墙或者咬到自己会死。这里用queue,和hashset记录目前所占的区域,queue主要负责更新区域,hashset主要负责查看会不会咬到自己。有一点注意的是有时下一步的位移是上一步的结尾,这时肯定是可行的,这时过早往hashset添加head是重复的,待会儿删除时,会把尾巴删掉,刚添加的头因为与尾巴相同,被删掉了,需要记得补回来。代码如下:
public class SnakeGame {    Queue<Integer> queue = new LinkedList<Integer>();    HashSet<Integer> hs = new HashSet<Integer>();    int[][] foods;    int foodIndex;    int width, height;    int currRow, currCol;

    /** Initialize your data structure here.        @param width - screen width        @param height - screen height         @param food - A list of food positions        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */    public SnakeGame(int width, int height, int[][] food) {        queue.offer(0);        hs.add(0);        this.foods = food;        this.foodIndex = 0;        this.width = width;        this.height = height;        currRow = 0;        currCol = 0;    }

    /** Moves the snake.        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down         @return The game's score after the move. Return -1 if game over.         Game over when snake crosses the screen boundary or bites its body. */    public int move(String direction) {        if (direction.equals('U')) {            currRow --;        } else if (direction.equals('D')) {            currRow ++;        } else if (direction.equals('L')) {            currCol --;        } else if (direction.equals('R')) {            currCol ++;        }        int head = currRow * width + currCol;        /*System.out.print(direction);        System.out.print(head);        System.out.println(queue.peek());        System.out.println(hs);*/        if (head != queue.peek() && hs.contains(head)) {            return -1;        }        if (currRow >= 0 && currRow < height && currCol >= 0 && currCol < width) {            queue.offer(head);            hs.add(head);            if (foodIndex < foods.length && currRow == foods[foodIndex][0] && currCol == foods[foodIndex][1]) {                foodIndex ++;            } else {                int trail = queue.poll();                hs.remove(trail);                if (head == trail)                    hs.add(head);            }            return foodIndex;        }        return -1;    }}

/** * Your SnakeGame object will be instantiated and called as such: * SnakeGame obj = new SnakeGame(width, height, food); * int param_1 = obj.move(direction); */
(0)

相关推荐

  • 十二生肖系列绘本 | 谁说蛇很高冷?快来看看贪吃的蛇小妹!

    自然界里有许多神秘的动物 蛇,就是其中之一 正因如此,蛇深受影视作品或名著小说的青睐 比如,<哈利·波特>中的终极Boss伏地魔 便将自己的一片灵魂附在了蛇身上 今天Professor要给 ...

  • 使用Opencv和Python构建贪吃蛇小游戏

    重磅干货,第一时间送达 来源丨https://blog.csdn.net/ZeroSwift/article/details/112172663 编辑丨AI算法与图像处理 导读 本文详细介绍贪吃蛇小游 ...

  • 不到 150 行代码写一个 Python 版的贪吃蛇

    来源:Python 技术「ID: pythonall」 相信大家小时候应该都玩过贪吃蛇这个游戏吧,反正我小时候超喜欢玩,没其他原因,因为家里的手机上只有这一个游戏可以消磨时光.后来随着移动互联网的普及 ...

  • 用python写一个简单的贪吃蛇游戏

    不知道有多少同学跟我一样,最初接触编程的动机就是为了自己做个游戏玩? Python 虽然并不是一个"为游戏而生"的语言,但也有着自己的游戏引擎.最常用的就是 pygame.另外还有 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战254:因子的组合

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战264:丑数 II

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...