首页 > 试题广场 >

小红的贪吃蛇

[编程题]小红的贪吃蛇
  • 热度指数：259 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红正在玩贪吃蛇游戏。游戏中小红需要控制蛇向上、下、左、右走，当蛇吃到食物时，蛇的身体会变长。当蛇撞到自己的身体时，游戏结束。当指令执行完毕时，游戏也结束。
本游戏和传统贪吃蛇不同的是，初始地图上就会存在所有的食物，吃完食物后也不能增加新的食物！
地图是无穷大的，因此没有撞墙这个说法。
假设蛇初始的坐标为(0,0)，初始长度是1（即只占用(0,0)这一个坐标）。
'W'指令代表向上移动，坐标由(x,y)移动到(x,y+1)。
'S'指令代表向下移动，坐标由(x,y)移动到(x,y-1)。
'A'指令代表向左移动，坐标由(x,y)移动到(x-1,y)。
'D'指令代表向右移动，坐标由(x,y)移动到(x+1,y)。
小红想知道，游戏结束的时候，蛇的长度是多少？

输入描述:
第一行输入一个正整数n，代表操作的指令长度。
第二行输入一个长度为n的，仅包含'W'、'A'、'S'、'D'四种字符的字符串。'W'代表蛇向上移动，'S'蛇向下移动，'A'代表蛇向左移动，'D'代表蛇向右移动。
第三行输入一个正整数m，代表食物的数量。
接下来的m行，每行输入两个整数x_i,y_i，代表每个食物的坐标。


保证蛇不会相反方向移动，例如，如果上一步蛇向上移动，那么下一步一定不会向下移动。
保证食物不会出现在(0,0)。保证没有两个食物的坐标重合。


输出描述:
一个正整数，代表游戏结束时蛇的长度。
示例1

输入

10
WASDDSAASD
3
2 0
-1 1
1 -1

输出

3

说明

蛇可以吃到两个食物，且过程中没有撞到自己的身体。最终长度为3。
示例2

输入

10
WWASDDDWAS
5
0 1
-1 1
-1 2
1 1
2 0

输出

5

说明

第五步向右时并不会撞到自己的身体，因为第五步向右到(0,1)时，位于(0,1)的尾巴正好离开了。
但第十步向下时会撞到自己的身体，游戏结束。
总共吃了4个食物，身体长度变成5。
算法知识视频讲解
添加回答
小狮子老黄头像 小狮子老黄 
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <utility>
#include <deque>
using namespace std;

/*
    主要使用了两套无序的哈希表来分别存储食物的位置和贪吃蛇的轨迹。使用哈希表是为了更快速地查找。并且使用一个队列来存储
    轨迹的先后顺序。每次到达一个新的位置的时候，就要先查看当前位置是否有食物，有的话蛇身长度加一，并且将存储食物的哈希
    表中擦除该位置的食物；然后比较轨迹中是否有当前位置，有的话就说明咬到了，游戏结束。
*/
struct pair_hash {
    template <class T1, class T2>
    size_t operator () (pair<T1, T2> const& pair) const {
        size_t h1 = hash<T1>()(
                        pair.first); //用默认的 hash 处理 pair 中的第一个数据 X1
        size_t h2 = hash<T2>()(
                        pair.second);//用默认的 hash 处理 pair 中的第二个数据 X2
        return h1 ^ h2; //异或，
    }
};

int main() {
    int n;
    cin >> n;
    string operation;
    cin>>operation;
    //cout << operation << " " << operation.size() << endl;
    int m;
    cin >> m;
    unordered_set<pair<int, int>, pair_hash> food;
    for (int i = 0; i < m; ++i) {
        int loc1, loc2;
        cin >> loc1 >> loc2;
        food.insert({loc1, loc2});
    }
    /*
    for(const auto& it : food) {
        cout << it.first << " " << it.second << endl;
    }
    */
    unordered_set<pair<int, int>, pair_hash> trace;
    deque<pair<int, int>> dq;
    trace.insert({0, 0});
    dq.push_back({0, 0});
    int cur_locx = 0, cur_locy = 0, body_len = 1;
    for (int i = 0; i < operation.size(); ++i) {
        if (operation[i] == 'W') {
            cur_locy += 1;
        } else if (operation[i] == 'S') {
            cur_locy -= 1;
        } else if (operation[i] == 'A') {
            cur_locx -= 1;
        } else {
            cur_locx += 1;
        }
        
        if (food.find({cur_locx, cur_locy}) != food.end()) {
            body_len += 1;
            food.erase({cur_locx, cur_locy});
        }
        //cout << "x = " << cur_locx << " " << " y = " << cur_locy << " body_len = " << body_len << endl;
        if (trace.size() >= body_len) {
            int old_x = dq.front().first, old_y = dq.front().second;
            dq.pop_front();
            trace.erase({old_x, old_y});
        }
        if (trace.find({cur_locx, cur_locy}) != trace.end()) {
            break;
        }
        trace.insert({cur_locx, cur_locy});
        dq.push_back({cur_locx, cur_locy});
    }
    cout << body_len;

    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2023-09-30 15:10:41 回复(0)
尼古拉nicola头像 尼古拉nicola
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
// 表示一个点
struct pos {
    pos() = default;
    pos(int _x, int _y): x(_x), y(_y) {}
    //重载==
    bool operator==(const pos& p) const {
        return this->x == p.x && this->y == p.y;
    }
    int x = 0, y = 0;
};

//重载哈希映射
class HashFunc {
  public:
    bool operator()(const pos& p) const {
        return hash<int>()(p.x)^hash<int>()(p.y);
    }
};

int main() {
    int n, m;
    string move;
    cin >> n >> move >> m;
    unordered_set<pos, HashFunc> food, bodyHash;  // 记录食物、身体的集合
    while (m--) {
        int x, y;
        cin >> x >> y;
        food.insert({x, y});
    }
    queue<pos> body;   // 队列先入先出模拟蛇的移动
    pos cur;
    bodyHash.insert(cur);
    body.push(cur);
    for (char& ch : move) {
        if (ch == 'W')
            cur.y += 1;
        else if (ch == 'S')
            cur.y -= 1;
        else if (ch == 'A')
            cur.x -= 1;
        else
            cur.x += 1;
        if (food.find(cur) != food.end()) {
            food.erase(cur);
        }
        else {
            bodyHash.erase(body.front());
            body.pop();
        }
        body.push(cur);  //要在判断碰撞之前在body中加入当前位置
        if (bodyHash.find(cur) != bodyHash.end()) { //撞了
            break;
        }
        bodyHash.insert(cur);
    }
    cout << body.size();
}
发表于 2023-03-17 16:03:11 回复(4)
想吃卤蛋的芹菜在收藏面经头像 想吃卤蛋的芹菜在收藏面经
不知道为啥只通过了12个用例,有没有大佬帮忙看看. 
#include <iostream>
using namespace std;

int main() {
    int step;
    cin>> step;
    string move;
    cin >> move;
    int food_num;
    cin >> food_num;
    int food[10000][2] = {};
    bool isFood = 0;
    bool isCrash = 0;
    for(int i = 0; i<food_num; i++)
    {
        cin>> food[i][0] >> food[i][1];   //0为横坐标, 1为纵坐标
    }

    int snake[10001][2] = {};
    snake[0][0] = 0;
    snake[0][1] = 0;
    int length = 1;
    int tempx,tempy = 0;


    for(int i = 0; i<step; i++)
    {
        if(isCrash == true)
        {
            break;
        }

        tempx = snake[length-1][0];
        tempy = snake[length-1][1];     //把尾巴的坐标保存起来

        for(int j =0; j<length-1; j++)    
            {
                snake[j+1][0] = snake[j][0] ;
                snake[j+1][1] = snake[j][1] ;     //蛇身坐标数列向后移动, 尾巴舍去, 头不变
                                                  //相当于除了头以外都沿蛇身向着头进行了移动
            }
        if(move[i] == 'W')
        {
            snake[0][1]++;                  //如果是W就把新头的纵坐标加1,下面同理
        }
        else if(move[i] == 'A')
        {
            snake[0][0]--;
        }
        else if(move[i] == 'S')
        {
            snake[0][1]--;
        }
         else if(move[i] == 'D')
        {
            snake[0][0]++;
        }
        
        for(int k = 0; k<food_num; k++)  //吃食物检测
        {
            if((snake[0][0]==food[k][0]) && (snake[0][1]==food[k][1]))   //如果吃到食物
            {
                length++; //长度增加
                snake[length-1][0] = tempx;
                snake[length-1][1] = tempy;    //把舍弃的尾巴加回到数列末尾(吃到食物相当于尾巴还在原位置)

                for(int m = 0; m<food_num-k-1; m++  )
                {
                    food[k+m][0] = food[k+m+1][0];
                    food[k+m][1] = food[k+m+1][1];   //食物坐标数列向前移动, 被吃掉的食物被舍弃了
                }
                food_num--;    //食物数量减少
                isFood = true;  
                break;    //食物不可能重叠, 吃到了就可以跳过剩余检测了
            }
        }

        for(int n = 3; n<length-1; n++)  //撞死检测, 由于机制问题蛇是不可能撞到头及其后面的两个点的
        {
            // if(isFood == true)
            // {
            //     break;  //不可能在吃到食物的同时撞死
            // }
            if((snake[0][0] == snake[n][0]) && (snake[0][1] == snake[n][1]))
            {
                isCrash = true;
                break; //撞到身体任意一个位置,游戏结束
            }
        }
        isFood = false;
    }

    cout << length << endl;

    return 0;

}
// 64 位输出请用 printf("%lld")


发表于 2023-07-17 11:07:42 回复(0)
3进制头像 3进制

思路：用队列模拟贪吃蛇的运动状态，并注意若前方没有食物，则尾部先向前移动，头部再向前移动；若前方有食物，则尾部不移动，头部向前移动

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static Map<Character, int[]> map = new HashMap<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        map.put('W', new int[]{0, 1});
        map.put('S', new int[]{0, -1});
        map.put('A', new int[]{-1, 0});
        map.put('D', new int[]{1, 0});
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            char[] op = in.next().toCharArray();
            int m = in.nextInt();
            List<String> food = new ArrayList<>();
            for(int i=0;i<m;i++){
                food.add(in.nextInt() + "-" + in.nextInt());
            }
            Deque<String> queue = new ArrayDeque<>();
            queue.offer("0-0");

            int res = 1;
            int[] curr = new int[]{0, 0};

            for(char x: op){
                // 记录当前贪吃蛇头即将到达的位置
                int[] dir = map.get(x);
                curr[0] += dir[0];
                curr[1] += dir[1];

                if(food.contains(curr[0]+"-"+curr[1])) {
                    res++;
                    queue.offer(curr[0]+"-"+curr[1]);
                    food.remove(curr[0]+"-"+curr[1]);
                }
                else {
                    queue.poll();
                    if(queue.contains(curr[0]+"-"+curr[1])){
                        break;
                    }else{
                        queue.offer(curr[0]+"-"+curr[1]);
                    }
                }
            }
            System.out.println(res);
        }
    }
}
发表于 2023-03-15 11:17:55 回复(1)
XXXXXXin425头像 XXXXXXin425 
n = int(input())
ops = input()
m = int(input())
food_pos = set()
for _ in range(m):
    i, j = list(map(int, input().split()))
    food_pos.add((i,j))

body_pos = [(0,0)]
for i in range(n):
    op = ops[i]
    if op == 'W':
        x, y = body_pos[-1][0], body_pos[-1][1]+1
    elif op == 'S':
        x, y = body_pos[-1][0], body_pos[-1][1]-1
    elif op == 'A':
        x, y = body_pos[-1][0]-1, body_pos[-1][1]
    else:
        x, y = body_pos[-1][0]+1, body_pos[-1][1]

    if (x,y) in body_pos[1:]:
        break
    if (x,y) in food_pos:
        food_pos.remove((x,y))
    else:
        body_pos.pop(0)
    body_pos.append((x,y))
    
    
print(len(body_pos))

发表于 2023-03-14 23:50:53 回复(0)
路旁清风头像 路旁清风
本题旨在模拟贪吃蛇游戏，需要维护贪吃蛇长度。由于贪吃蛇的运动可以简化为头到某个坐标，尾巴离开某个坐标，因此考虑使用队列维护。以下为本题的解答： 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String l1 = in.nextLine();
        int num = Integer.parseInt(l1);
        String op = in.nextLine();
        String l3 = in.nextLine();
        int foodnum = Integer.parseInt(l3);
        Vector<String> food = new Vector<>(foodnum);
        for(int i=0;i<foodnum;i++){
            String pos = in.nextLine();
            String p[] = pos.split(" ");
            food.add((Integer.parseInt(p[0]))+"-"+((Integer.parseInt(p[1]))));
        }
        int x=0,y=0,res=0;
        Deque<String> snake = new ArrayDeque<>(num);
        snake.add("0-0");
        for(int i=0;i<num;i++){
            switch (op.charAt(i)){
                case 'W':
                    y+=1;
                    if(food.contains(x+"-"+y)) {
                        snake.add(x+"-"+y);
                        food.remove(x+"-"+y);
                    }
                    else {
                        snake.pop();
                        if(snake.contains(x+"-"+y)){
                            res=1;
                            i=num-1;
                        }else{
                            snake.add(x+"-"+y);
                        }
                    }
                    break;
                case 'A':
                    x-=1;
                    if(food.contains(x+"-"+y)) {
                        snake.add(x+"-"+y);
                        food.remove(x+"-"+y);
                    }
                    else {
                        snake.pop();
                        if(snake.contains(x+"-"+y)){
                            res=1;
                            i=num-1;
                        }else{
                            snake.add(x+"-"+y);
                        }
                    }
                    break;
                case 'S':
                    y-=1;
                    if(food.contains(x+"-"+y)) {
                        snake.add(x+"-"+y);
                        food.remove(x+"-"+y);
                    }
                    else {
                        snake.pop();
                        if(snake.contains(x+"-"+y)){
                            res=1;
                            i=num-1;
                        }else{
                            snake.add(x+"-"+y);
                        }
                    }
                    break;
                case 'D':
                    x+=1;
                    if(food.contains(x+"-"+y)) {
                        snake.add(x+"-"+y);
                        food.remove(x+"-"+y);
                    }
                    else {
                        snake.pop();
                        if(snake.contains(x+"-"+y)){
                            res=1;
                            i=num-1;
                        }else{
                            snake.add(x+"-"+y);
                        }
                    }
                    break;
            }
        }
        res += snake.size();
        System.out.println(res);
    }
}
值得注意的有以下两个点：
1.食物被吃后需要更新食物状态
2.要搞清楚蛇的运动分解，搞清先后顺序

发表于 2023-03-13 20:45:54 回复(0)
提交观点

问题信息

来自：22年秋招蚂蚁编程题精选
难度：
6条回答 1989浏览

热门推荐

通过挑战的用户

相关试题

小红的贪吃蛇

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号