pen22

LeetCode - 29.顺时针打印矩阵

发表于 分类于 阅读次数： Valine：

题面

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

样例

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
1
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]
1
2
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

思路

直接按照题意转就好了，这道题虽然标的Easy，但还是被空向量和数据范围不明确给坑了一下。。

没有数据范围，我直接把访问过的地方标记 $0x3f3f3f3f$ 但其实这种做法是不对的，正确的做法是使用另一个 $vis$ 数组，$vis[i][j]$ 表示$i,j$ 这个位置输出过了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool ok(int x, int y, int n, int m) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int n = matrix.size(); if(n == 0) return {};
    int m = matrix[0].size();
    vector<int> ans(n * m);
    int cnt = 0, tmp = 0, inf = 0x3f3f3f3f;
    int x = 0, y = 0;
    int d[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    ans[cnt++] = matrix[0][0];
    matrix[x][y] = inf;
    while(cnt < n * m) {
        while(ok(x + d[tmp][0], y + d[tmp][1], n, m) && matrix[x + d[tmp][0]][y + d[tmp][1]] != inf) {
            ans[cnt++] = matrix[x + d[tmp][0]][y + d[tmp][1]];
            matrix[x + d[tmp][0]][y + d[tmp][1]] = inf;
            x += d[tmp][0];
            y += d[tmp][1];
        }
        tmp = (tmp + 1) % 4;
    }
    return ans;
}