README.md

comments	difficulty	edit_url	rating	source	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3248.Snake%20in%20Matrix/README.md	1171	第 410 场周赛 Q1	数组 字符串 模拟

3248. 矩阵中的蛇

English Version

题目描述

大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。

蛇从单元格 0 开始，并遵循一系列命令移动。

给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 "UP"、"RIGHT"、"DOWN" 和 "LEFT"。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。

返回执行 commands 后蛇所停留的最终单元格的位置。

 

示例 1：

输入：n = 2, commands = ["RIGHT","DOWN"]

输出：3

解释：

0	1
2	3

0	1
2	3

0	1
2	3

示例 2：

输入：n = 3, commands = ["DOWN","RIGHT","UP"]

输出：1

解释：

0	1	2
3	4	5
6	7	8

0	1	2
3	4	5
6	7	8

0	1	2
3	4	5
6	7	8

0	1	2
3	4	5
6	7	8

 

提示：

• 2 <= n <= 10
• 1 <= commands.length <= 100
• commands 仅由 "UP"、"RIGHT"、"DOWN" 和 "LEFT" 组成。
• 生成的测评数据确保蛇不会移动到矩阵的边界外。

解法

方法一：模拟

我们可以用两个变量 $x$ 和 $y$ 来表示蛇的位置，初始时 $x = y = 0$，然后遍历 $\textit{commands}$，根据当前的命令更新 $x$ 和 $y$ 的值，最后返回 $x \times n + y$ 即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\textit{commands}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def finalPositionOfSnake(self, n: int, commands: List[str]) -> int:
        x = y = 0
        for c in commands:
            match c[0]:
                case "U":
                    x -= 1
                case "D":
                    x += 1
                case "L":
                    y -= 1
                case "R":
                    y += 1
        return x * n + y

Java

class Solution {
    public int finalPositionOfSnake(int n, List<String> commands) {
        int x = 0, y = 0;
        for (var c : commands) {
            switch (c.charAt(0)) {
                case 'U' -> x--;
                case 'D' -> x++;
                case 'L' -> y--;
                case 'R' -> y++;
            }
        }
        return x * n + y;
    }
}

C++

class Solution {
public:
    int finalPositionOfSnake(int n, vector<string>& commands) {
        int x = 0, y = 0;
        for (const auto& c : commands) {
            switch (c[0]) {
            case 'U': x--; break;
            case 'D': x++; break;
            case 'L': y--; break;
            case 'R': y++; break;
            }
        }
        return x * n + y;
    }
};

Go

func finalPositionOfSnake(n int, commands []string) int {
	x, y := 0, 0
	for _, c := range commands {
		switch c[0] {
		case 'U':
			x--
		case 'D':
			x++
		case 'L':
			y--
		case 'R':
			y++
		}
	}
	return x*n + y
}

TypeScript

function finalPositionOfSnake(n: number, commands: string[]): number {
    let [x, y] = [0, 0];
    for (const c of commands) {
        c[0] === 'U' && x--;
        c[0] === 'D' && x++;
        c[0] === 'L' && y--;
        c[0] === 'R' && y++;
    }
    return x * n + y;
}