Spiral Matrix III: เมทริกซ์เกลียว 3 ใน C++

ปัญหา

กริด R × C เริ่มที่ (r0, c0) หน้าทิศตะวันออก เดินแบบ Spiral (Clockwise) เยี่ยมทุกเซลล์ในกริด (อาจเดินนอกกริดไปก่อน) คืนลำดับ Seat ที่เยี่ยม

แนวคิด: Simulate Spiral Walk

Direction Vectors

dir = 0: East  (0, +1)
dir = 1: South (+1, 0)
dir = 2: West  (0, -1)
dir = 3: North (-1, 0)

Step Length Pattern

1, 1, 2, 2, 3, 3, 4, 4, ...

→ ทิศ East/West (dir 0,2) เพิ่ม Step Length ทุกครั้ง

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};  // E, S, W, N

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> result;
        int stepLen = 0;
        int dir = 0;
        
        result.push_back({r0, c0});
        
        while (result.size() < R * C) {
            if (dir == 0 || dir == 2) stepLen++;  // E หรือ W เพิ่มความยาว
            
            for (int i = 0; i < stepLen; i++) {
                r0 += dirs[dir][0];
                c0 += dirs[dir][1];
                
                if (r0 >= 0 && r0 < R && c0 >= 0 && c0 < C) {
                    result.push_back({r0, c0});
                }
            }
            dir = (dir + 1) % 4;
        }
        return result;
    }
};

void printVector(const vector<vector<int>>& v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[" << v[i][0] << "," << v[i][1] << "]";
        if (i < v.size()-1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution ob;
    auto res = ob.spiralMatrixIII(5, 5, 1, 3);
    printVector(res);
    return 0;
}

Output สำหรับ 5×5 เริ่ม (1,3)

[[1,3],[1,4],[2,4],[2,3],[2,2],[1,2],[0,2],[0,3],[0,4],
 [3,4],[3,3],[3,2],[3,1],[2,1],[1,1],[0,1],
 [4,4],[4,3],[4,2],[4,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

ความซับซ้อน

• Time: O(R × C) - เยี่ยมทุกเซลล์ในกริด 1 ครั้ง
• Space: O(R × C) - เก็บผลลัพธ์

Input / Output

Input:  R=5, C=5, r0=1, c0=3
Output: 25 coordinates in spiral order