Leetcode 54 - Spiral Matrix

題目

Problem#

給你一個 $n \times m$ 的矩陣，要你以迴旋順序回傳

• 測資限制:
  • $1 \le m, n \le 10$
  • $-100 \le M[i] \le 100$

想法#

模擬即可，可以記錄已經訪問過的 (i, j)，假如全部都訪問過則結束

• 時間複雜度: $\mathcal{O}(n^2)$
• 空間複雜度: $\mathcal{O}(n^2)$

AC Code#

Copy

using P=pair<int,int>;
#define X first
#define Y second
#define N 100
 
class Solution {
public:
    int n, m;
    bool vis[N+5];
    bool isEnd()
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(!vis[i*m+j])
                    return false;
        return true;
    }
    vector<int> spiralOrder(vector<vector<int>>& M)
    {
        vector<int> ans;
        n = M.size(), m = M[0].size();
        int i = 0, j = 0;
        int dir = 0;
        P dirOff[4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
 
        auto check = [&](int i, int j)
        {
            return (0 <= i && i < n && 0 <= j && j < m) && !vis[i*m+j];
        };
 
        ans.push_back(M[0][0]);
        vis[0] = true;
 
        ans.reserve(n*m);
        while(!isEnd())
        {
            int ni = i + dirOff[dir].X,
                nj = j + dirOff[dir].Y;
            if(!check(ni, nj))
            {
                dir++;
                if(dir >= 4)
                    dir -= 4;
                continue;
            }
            else
            {
                i = ni;
                j = nj;
                ans.push_back(M[i][j]);
                vis[i*m+j] = true;
            }
        }
        return ans;
    }
};

view raw leetcode/54.cpp delivered with ❤ by emgithub