跳转至

3248. 矩阵中的蛇

题目描述

大小为 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" 组成。
  • 生成的测评数据确保蛇不会移动到矩阵的边界外。

解法

方法一：模拟

思考

在 \(n\times n\) 网格按指令移动，保证不越界。\(n\le 10\)、\(\textit{commands}\) 至多 \(100\)，按字面模拟即可。

维护坐标 \((x,y)\)，由命令首字母改一行或一列，最后返回 \(x\times n+y\)。无需建盘。

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

评论