# 59 - Spiral Matrix II

解法一 - 用 #54 的解法一走過整個矩陣，邊走邊依序賦值

這個解法滿直觀的，實作如下：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        // Create the matrix first
        // Use the same while loop to traverse throguh all matrix element
        // Assign value to each element

        vector<vector<int>> res(n, std::vector<int>(n));;
        if(n == 0) return res;

        int r1=0, r2=n-1, c1=0, c2=n-1, val=1;

        // if use (r1<r2 && c1<c2), will miss the middle element
        while(r1<=r2 && c1<=c2) {
            for(int c=c1; c<=c2; c++) { res[r1][c] = val; val++;}
            for(int r=r1+1; r<=r2; r++) { res[r][c2] = val; val++;}

            if(r1<r2 && c1<c2) {
                for(int c=c2-1; c>=c1; c--) { res[r2][c] = val; val++;}
                for(int r=r2-1; r>=r1+1; r--) { res[r][c1] = val; val++;}
            }

            r1++;
            r2--;
            c1++;
            c2--;
        }

        return res;
    }
};

解法二 - 用模擬的方式走

這個演算法的核心精神是，每當走到已經有值的矩陣位置時，就向右轉。實作如下：

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        if(n == 0) return res;

        int r=0, c=0, dr=0, dc=1; //(dr, dc) is the direction
        for(int k=1; k<=n*n; k++) {
            res[r][c] = k;

            if(res[(r+dr+n)%n][(c+dc+n)%n]) {
                int tmpdc = dc;
                dc = -dr;
                dr = tmpdc;
            }

            r += dr;
            c += dc;
        }

        return res;
    }
};

兩個問題：

1. 為什麼要用 res[(r+dr+n)%n][(c+dc+n)%n] 檢查？

   解釋寫在這邊：
2. 為什麼換方向時，是 dc = -dr, dr = dc？