Diagonal Traverse เรียงเมทริกซ์แบบเฉียงใน C++

ให้เมทริกซ์ M×N เรียงสมาชิกตามทิศทางเฉียง (zigzag diagonal)

ตัวอย่าง: [[1,2,3],[4,5,6],[7,8,9]] → [1,2,4,7,5,3,6,8,9]

วิธีแก้ปัญหา (Diagonal Grouping)

1. แบ่งเมทริกซ์เป็นแนวทแยง: เริ่มจากแถวแรกทุกคอลัมน์ แล้วคอลัมน์สุดท้ายทุกแถว
2. สลับทิศทาง (reverse) ทุกแนวทแยงสลับกัน
3. รวมผลลัพธ์

ตัวอย่างโค้ด C++

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int n = matrix.size();
        int m = n ? matrix[0].size() : 0;
        bool down = false;
        
        // แนวทแยงเริ่มจากแถวแรก
        for (int i = 0; i < n; i++) {
            int x = i, y = 0;
            vector<int> temp;
            while (x >= 0 && y < m) {
                temp.push_back(matrix[x][y]);
                x--; y++;
            }
            if (down) reverse(temp.begin(), temp.end());
            for (int val : temp) ret.push_back(val);
            down = !down;
        }
        
        // แนวทแยงเริ่มจากคอลัมน์สุดท้าย (ยกเว้นมุมซ้ายบน)
        for (int i = 1; i < m; i++) {
            int x = n - 1, y = i;
            vector<int> temp;
            while (x >= 0 && y < m) {
                temp.push_back(matrix[x][y]);
                x--; y++;
            }
            if (down) reverse(temp.begin(), temp.end());
            for (int val : temp) ret.push_back(val);
            down = !down;
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
    Solution ob;
    print_vector(ob.findDiagonalOrder(v));
    return 0;
}

Input

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

Output

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