# 54-Spiral Matrix
###### tags: `Medium`
## Question
https://leetcode.com/problems/spiral-matrix/

## Key
1. s2想法: 將四個頂點設為變量，再用四個迴圈依序在頂點與頂點間取值。每次縮進一個長方形。注意考慮最後可能有剩餘一條線的情況。
2. s1想法:每個邊迭代完會就紀錄結束的x,y座標(每次x或y其中一個會等於下一次迭代的固定值，另一個則遞增或遞減)，可以觀察到規律:一個正方形做spiral traverse是兩個邊index先遞增 兩個邊index再遞減

## Solution
### s1

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& arr) {
        vector<int>v1;
        int m=arr.size();
        int n=arr[0].size();
        int x=0,y=n-1,z=m-1,p=0;
        int i,j;
        int c=1;
        while(c<=(n*m))
        {
            i=x;
            for(j=p;j<=y&&c<=(n*m);j++)
            {
                v1.push_back(arr[i][j]);
            c++;
            }
            x++;
            j=y;
            for(i=x;i<=z&&c<=(n*m);i++)
            {
               v1.push_back(arr[i][j]);
                 c++;           
            }
            y--;
            i=z;
            for(j=y;j>=p&&c<=(n*m);j--)
            {
               v1.push_back(arr[i][j]);
               c++;
            }
            z--;
            j=p;
            for(i=z;i>=x&&c<=(n*m);i--)
            {
                 v1.push_back(arr[i][j]);
                c++;
            }
            p++;
        }
        return v1;
    }
};

### s2

vector<int> spiralTraverse(vector<vector<int>> array) {
  // Write your code here.
  if (array.size() == 0)
      return {};
  vector<int> answer;
  int startRow = 0;
  int endRow = array.size() - 1;
  int startColumn = 0;
  int endColumn = array[0].size() - 1;
	
  while (startRow <= endRow && startColumn <= endColumn){
      for (int col = startColumn; col <= endColumn; col++){
          answer.push_back(array[startRow][col]);
      }
      for (int row = startRow + 1; row <= endRow; row++){
          answer.push_back(array[row][endColumn]);
      }
      for (int col = endColumn - 1; col >= startColumn; col--){
          if (endRow == startRow)
              break;
          answer.push_back(array[endRow][col]);
      }
      for (int row = endRow - 1; row > startRow; row--){
          if (endColumn == startColumn)
              break;
          answer.push_back(array[row][startColumn]);
      }
      startRow++;
      endRow--;
      startColumn++;
      endColumn--;
  }
  return answer;
}