【LeetCode】 59. Spiral Matrix II

Description

Given a positive integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

給一個正整數n，請產生一個方陣，照螺旋的順序填入1到n^2。

Example:

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution

• 用一個變數i去紀錄現在產生到哪裡。
• 用變數x和y去紀錄現在的位置。
• 用變數dir去控制下一次的位置。
• 演算法分成三步驟：
  • 填入矩陣
  • 更新方向
  • 更新位置
• 填入矩陣後判斷是否完成。
• 更新方向需要先判斷下一步是否合法，如果不合法才改變方向，否則就照原方向繼續走。

Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n,vector<int>(n,0));
        
        int x=0,y=0;
        int dir=0;
        for(int i=1;;i++)
        {
            //set
            ans[y][x]=i;
            if(i==n*n)
                break;
            //control dir
            while(1)
            {
                if(dir%4==0)
                {
                    if(x!=n-1 && ans[y][x+1]==0)
                        break;
                }
                else if(dir%4==1)
                {
                    if(y!=n-1 && ans[y+1][x]==0)
                        break;
                }
                else if(dir%4==2)
                {
                    if(x!=0 && ans[y][x-1]==0)
                        break;
                }
                else
                {
                    if(y!=0 && ans[y-1][x]==0)
                        break;
                }
                dir++;
            }
            
            //move
            if(dir%4==0)
            {
                x++;
            }
            else if(dir%4==1)
            {
                y++;
            }
            else if(dir%4==2)
            {
                x--;
            }
            else
            {
                y--;
            }
        }
        
        return ans;
    }
};

tags: LeetCode C++