[LeetCode] 885. 螺旋矩阵 III

在rows*cols的网格上，从单元格(r_Start, c_Start)面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。

最终，遍历网格中的所有的 rows x cols 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：rows = 1, cols = 4, rStart = 0, cStart = 0
输出：[[0,0],[0,1],[0,2],[0,3]]

示例 2：

输入：rows = 5, cols = 6, rStart = 1, cStart = 4

输出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

提示：

1 <= rows,cols <= 100
0 <= rStart < rows
0 <= cStart < cols

思路:

仍然是4条边恒定方向，抽象成4种操作顶边向右访问、右边向下访问、左边向上访问和底边向左访问。只不过这次各边不是向内收缩，而是向外扩展；同时需要不断判断是否出界，所以需要单独添加一个 isInMatrix(int r, int c, int rows, int cols)函数。

AC代码:

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> result;
        int layerTop = rStart, layerBottom = rStart;
        int layerLeft = cStart, layerRight = cStart;

        int r = rStart, c = cStart;
        result.push_back({r, c});
        
        while (result.size() < rows * cols) {
            
            // === 扩展东边：layerRight++，然后从当前位置走过去 ===
            layerRight++;
            while (c < layerRight) {  // 向东走到新边界
                c++;
                if (isInMatrix(r, c, rows, cols)) result.push_back({r, c});
            }
            
            // === 扩展南边：layerBottom++，然后向南走 ===
            layerBottom++;
            while (r < layerBottom) {
                r++;
                if (isInMatrix(r, c, rows, cols)) result.push_back({r, c});
            }
            
            // === 扩展西边：layerLeft--，然后向西走 ===
            layerLeft--;
            while (c > layerLeft) {
                c--;
                if (isInMatrix(r, c, rows, cols)) result.push_back({r, c});
            }
            
            // === 扩展北边：layerTop--，然后向北走 ===
            layerTop--;
            while (r > layerTop) {
                r--;
                if (isInMatrix(r, c, rows, cols)) result.push_back({r, c});
            }
        }
        
        return result;
    }
private:
    bool isInMatrix(int r, int c, int rows, int cols) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }
};Code language: C++ (cpp)

我在网上查到的另一种的写法是:

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> result;
        // 方向：右(东)、下(南)、左(西)、上(北)
        int dr[] = {0, 1, 0, -1};
        int dc[] = {1, 0, -1, 0};
        
        int r = rStart, c = cStart;  // 当前位置
        int steps = 1;                // 当前步长
        int dir = 0;                  // 当前方向
        
        result.push_back({r, c});     // 起点
        
        while (result.size() < rows * cols) {
            // 每个步长走两次（两个方向）
            for (int i = 0; i < 2; i++) {
                // 往当前方向走 steps 步
                for (int j = 0; j < steps; j++) {
                    r += dr[dir];
                    c += dc[dir];
                    // 如果在网格内，加入结果
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        result.push_back({r, c});
                    }
                }
                dir = (dir + 1) % 4;  // 顺时针转方向
            }
            steps++;  // 两个方向走完，步长+1
        }
        
        return result;
    }
};Code language: C++ (cpp)