题解 | 贪吃蛇游戏

import java.util.*;

/**
 * @author supermejane
 * @date 2025/10/1
 * @description 牛客noob130 贪吃蛇游戏
 */
public class Main {
    static Deque<int[]> snake = new ArrayDeque<>();
	
  	//存储四个方向
    private static HashMap<Integer, List<Integer>> direct = new HashMap<>();
	//记录当前贪吃蛇占的位置
    private static HashSet<String> pos = new HashSet<>();
	//输入snack初始化pos
	static {
		  direct.put(1, Arrays.asList(0, 1));
		  direct.put(2, Arrays.asList(0, -1));
		  direct.put(3, Arrays.asList(-1, 0));
		  direct.put(4, Arrays.asList(1, 0));
	}
    private static void initpos(Deque<int[]> snack) {
        Iterator<int[]> iterator = snack.iterator();
        while (iterator.hasNext()) {
            int[] e = iterator.next();
            pos.add(array2Str(e));
        }
    }

    private static String array2Str(int[] e) {
        return String.valueOf(e[0]) + "-" + String.valueOf(e[1]);
    }
  
    public static boolean moveSnake(int dir) {
        int[] newHead = new int[2];
        newHead[0] = snake.getFirst()[0] + direct.get(dir).get(0);
        newHead[1] = snake.getFirst()[1] + direct.get(dir).get(1);
        int[] oldTail = snake.getLast();

        if (isCollapse(snake, newHead, oldTail)) {
            return true;
        }

        snake.addFirst(newHead);
        pos.remove(array2Str(snake.getLast()));
        snake.pollLast();
	  	//最后加入是一定不会出错的，放在前面的话可能会被pos.remove删除
        pos.add(array2Str(newHead));

        return false;
    }
	
  	//检查是否发生碰撞，exclude是为了排除移动之前的Tail
    public static boolean isCollapse(Deque<int[]> snake, int[] newHead, int[] exclude) {
        if (snake.size() <= 1) return false;
        String newHeadStr = array2Str(newHead);
        String excludeStr = exclude != null ? array2Str(exclude) : null;
        if (pos.contains(newHeadStr) && !newHeadStr.equals(excludeStr)) {
            return true;
        }
        return false;
    }

    public static boolean eatSnake(int dir) {
        int[] newHead = new int[2];
        newHead[0] = snake.getFirst()[0] + direct.get(dir).get(0);
        newHead[1] = snake.getFirst()[1] + direct.get(dir).get(1);

        if (isCollapse(snake, newHead, null)) {
            return true;
        }

        snake.addFirst(newHead);
        pos.add(array2Str(newHead));

        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        snake.clear();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            snake.addFirst(new int[] {x, y}); //这里把题目自带的addLast改成addFirst
        }
	  	//
        initpos(snake);
        for (int i = 0; i < q; i++) {
            int op = sc.nextInt();
            int dir = sc.nextInt();
            boolean collision = (op == 1 ? moveSnake(dir) : eatSnake(dir));
            if (collision) {
                System.out.println(-1);
                sc.close();
                return;
            } else {
			  	//改成从头开始遍历
                Iterator<int[]> it = snake.iterator();
                while (it.hasNext()) {
                    int[] p = it.next();
                    System.out.println(p[0] + " " + p[1]);
                }
            }
        }
        sc.close();
    }
}