方向数组的应用

54. 螺旋矩阵

Difficulty: 中等

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

Solution

class Solution {
public:
    static const int N = 10;
    bool used[N][N] = {};
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> res;
        for (int x = 0, y = 0, cnt = 0, d = 0; cnt < m*n; ++cnt) {
            res.push_back(matrix[x][y]);
            used[x][y] = true;//重要，不要漏
            int a = x + dx[d], b = y + dy[d];
            if(a < 0 || a >= m || b < 0 || b >= n || used[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

59. 螺旋矩阵 II

Difficulty: 中等

给你一个正整数 n ，生成一个包含 1 到 n<sup>2</sup> 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

Solution

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        vector<vector<bool>> used(n, vector<bool>(n));
        int d[4][4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int cnt = 1, x = 0, y = 0, dir = 0, end = n * n; cnt <= end; ++cnt) {
            res[x][y] = cnt;
            used[x][y] = true;
            int a = x + d[dir][0], b = y + d[dir][1];
            if (a < 0 || a >= n || b < 0 || b >= n || used[a][b]) {// used[a][b]要放最后，用到了下标a,b
                dir = (dir + 1) % 4;
                a = x + d[dir][0], b = y + d[dir][1];
            }
            x = a, y = b;
        } 
        return res;
    }
};

5911. 模拟行走机器人 II

Difficulty: 中等

给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。

机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。

1. 沿着当前方向尝试 往前一步 。
2. 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。

如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。

请你实现 Robot 类：

• Robot(int width, int height) 初始化一个 width x height 的网格图，机器人初始在 (0, 0) ，方向朝 "East" 。
• void move(int num) 给机器人下达前进 num 步的指令。
• int[] getPos() 返回机器人当前所处的格子位置，用一个长度为 2 的数组 [x, y] 表示。
• String getDir() 返回当前机器人的朝向，为 "North" ，"East" ，"South" 或者 "West" 。

示例 1：

输入：
["Robot", "move", "move", "getPos", "getDir", "move", "move", "move", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]

解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.move(2);  // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.move(2);  // 朝东移动 1 步到达 (5, 0) ，并朝东。
                // 下一步继续往东移动将出界，所以逆时针转变方向朝北。
                // 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.move(1);  // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.move(4);  // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
                // 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"

提示：

• 2 <= width, height <= 100
• 1 <= num <= 10<sup>5</sup>
• move ，getPos 和 getDir **总共 **调用次数不超过 10<sup>4</sup> 次。

Solution

class Robot {
public:
    int w, h;
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};// 方向数组
    int d; //当前方向
    int x, y;//当前坐标
    Robot(int width, int height) {
        w = width, h = height, x = y = d = 0;
    }
    
    void move(int num) {
        while (num--) {
            while (x + dx[d] < 0 || x + dx[d] >= w || y + dy[d] < 0 || y + dy[d] >= h) d = (d + 1) % 4;//如果下一步越界就更换方向，直到不越界
            x += dx[d], y += dy[d];// 更新位置走到下一步
            if (x == 0 || x == w - 1 || y == 0 || y == h - 1) break;//走到边界后，后面都是绕外圈重复不停的转圈，取模后再走
        }
        num = num % (2 * w + 2 * h - 4);// 步数取模
        while (num--) {//继续走
            while (x + dx[d] < 0 || x + dx[d] >= w || y + dy[d] < 0 || y + dy[d] >= h) d = (d + 1) % 4;
            x += dx[d], y += dy[d];
        }
    }
    
    vector<int> getPos() {
        return {x, y};
    }
    
    string getDir() {
        if (d == 0) return "East";
        if (d == 1) return "North";
        if (d == 2) return "West";
        if (d == 3) return "South";
        return "";
    }
};