[LeetCode] 54. Spiral Matrix

• Problem: Spiral Matrix, 用 vector 給定一個二維陣列, 順時針螺旋的方式, 將所有元素 traverse 一次
• Concept: 注意邊界的處理, 轉彎的動作包含了
• 超過邊界: 判斷是否超過 minX, maxX 及 Y 方向的邊界
• 返回界內
• 轉彎: 可以用 enum 來寫 direction
• 更新邊界: e.g. 往下走, 則上界 minY += 1
• Implementation:

• class Solution {
  public:
      enum E_DIRECTION {
          E_DIR_RIGHT = 0,
          E_DIR_DOWN,
          E_DIR_LEFT,
          E_DIR_UP,
          E_DIR_ALL
      };
      
      enum E_TOWARD {
          E_FORWARD = 0,
          E_BACKWARD,
          E_TOWARDS
      };
      
      void step (E_DIRECTION dir, E_TOWARD to, int &x, int &y) {
          int step = (E_FORWARD == to) ? 1 : -1;
          switch (dir) {
              case E_DIR_RIGHT:
                  x += step;
                  break;
              case E_DIR_DOWN:
                  y += step;
                  break;
              case E_DIR_LEFT:
                  x -= step;
                  break;
              case E_DIR_UP:
                  y -= step;
                  break;
          }
      }
      
      void turn (E_DIRECTION &dir, int &minX, int &maxX, int &minY, int &maxY) {
          int nextDir = (1 + dir) % E_DIR_ALL;
          dir = (E_DIRECTION) nextDir;
          switch (dir) {
              case E_DIR_DOWN:
                  minY += 1;
                  break;
              case E_DIR_LEFT:
                  maxX -= 1;
                  break;
              case E_DIR_UP:
                  maxY -= 1;
                  break;
              case E_DIR_RIGHT:
                  minX += 1;
                  break;
          }
      }
      
      vector spiralOrder(vector>& matrix) {
          vector result;
          if (matrix.empty()) return result;
          
          int height = matrix.size();
          int width = matrix[0].size();  // check matrix.empty before
          int x = 0, y = 0;   // current traverse coordinate
          int minX = 0, maxX = width - 1, minY = 0, maxY = height - 1;
          E_DIRECTION eDir = E_DIR_RIGHT;     
          
          // termination condition
          while (minX <= maxX && minY <= maxY) {
              // change direction condition
              if (x < minX || x > maxX || y < minY || y > maxY) {
                  step (eDir, E_BACKWARD, x, y);
                  turn (eDir, minX, maxX, minY, maxY);
                  step (eDir, E_FORWARD, x, y);
              } else {
                  // index starts from 1
                  result.push_back(matrix[y][x]);
                  step (eDir, E_FORWARD, x, y);
              }
          }
          return result;
      }
  };