​LeetCode刷题实战353:贪吃蛇

程序IT圈

共 7377字,需浏览 15分钟

 ·

2021-08-20 00:02

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

今天和大家聊的问题叫做 贪吃蛇,我们先来看题面:
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);
 */


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-340题汇总,希望对你有点帮助!
LeetCode刷题实战341:扁平化嵌套列表迭代器
LeetCode刷题实战342:4的幂
LeetCode刷题实战343:整数拆分
LeetCode刷题实战344:反转字符串
LeetCode刷题实战345:反转字符串中的元音字母
LeetCode刷题实战346:数据流中的移动平均值
LeetCode刷题实战347:前 K 个高频元素
LeetCode刷题实战348:设计井字棋
LeetCode刷题实战349:两个数组的交集
LeetCode刷题实战350:两个数组的交集 II
LeetCode刷题实战351:安卓系统手势解锁

浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报