原題：885. Spiral Matrix III

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.
Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.
Now, we walk in a clockwise spiral shape to visit every position in this grid.
Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)
Eventually, we reach all R * C spaces of the grid.
Return a list of coordinates representing the positions of the grid in the order they were visited.

題目大意：

給定一個(gè) R*C的矩陣，以及初始坐標(biāo)(r0, c0), 你開始面向東凛虽，以順時(shí)針方向做螺旋運(yùn)動，當(dāng)你走完所有的點(diǎn)后鲜屏，要求記錄你所走的軌跡风范，如下圖所示
示例1：

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

e.g. 1

示例2：

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[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]]

e.g. 2

解題思路：

通過示例2的圖我們可以觀察到抵屿，我們是先往東走1步聚唐，再往南走一步丐重，然后再往西走2步，再往北走2步杆查，之后再往東走3步扮惦，再往南走3步，可以看到其走的步數(shù)是 1,1,2,2,3,3,4,4,5,5,6,6.....亲桦；我們以一圈為一組崖蜜，即往東南西北四個(gè)方向都走一遍為1組，即1,1,2,2 |,3,3,4,4 |,5,5,6,6|.....客峭；
往東走對應(yīng)坐標(biāo)變化：(0, +1)
往南走對應(yīng)坐標(biāo)變化：(+1, 0)
往西走對應(yīng)坐標(biāo)變化：(0, -1)
往北走對應(yīng)坐標(biāo)變化：(-1, 0)
因此可以：dx = {0, 1, 0, -1}; dy = {1, 0, -1, 0};
然后每一組逐一遍歷往哪個(gè)方向(r0 + dx[i], c0 + dy[i])走幾步即可

代碼如下：

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) 
    {
        vector<vector<int> > ans = {{r0, c0}};
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int dk = 1;
        for(int i = 1; i < 2 * R * C; i += 2)
        {
            for(int j = 0; j < 4; j++)
            {
                dk = i + j / 2;
                for(int k = 0; k < dk; k++)
                {
                    r0 += dx[j];
                    c0 += dy[j];
                    if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                        ans.push_back({r0,c0});
                    if(ans.size() == R*C)
                        return ans;
                }
            }
        }
    }
};

代碼2：

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) 
    {
        vector<vector<int> > ans = {{r0, c0}};
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int num=0, steps=1;
        while(ans.size() < R * C)
        {
            for(int i = 0; i < 4; i++)
            {
                for(int j = 0; j < steps; j++)
                {
                    r0 += dx[i];
                    c0 += dy[i];
                    if(r0 >= 0 && r0 < R && c0 >= 0 && c0 < C)
                        ans.push_back({r0, c0});
                }
                num++;
                if(num%2==0)
                    steps++;
            }
        }
        return ans;
    }
};