Shift 2D Grid: เลื่อนกริด 2 มิติใน C++

ปัญหา

กริด m × n เลื่อน (Shift) k ครั้ง กฎการเลื่อน:

1. grid[i][j] → grid[i][j+1]
2. grid[i][n-1] → grid[i+1][0]
3. grid[m-1][n-1] → grid[0][0]

กล่าวคือ Flatten เป็น 1D Array แล้ว Rotate Right k ครั้ง

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

แนวคิด: Flatten + Rotate + Reshape

วิธีที่ 1: Simulate ทีละ Step (เข้าใจง่าย แต่ช้า O(k×mn))

void shift(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int last = grid[m-1][n-1];
    for (int i = m-1; i >= 0; i--) {
        for (int j = n-1; j >= 0; j--) {
            if (j == 0 && i > 0) grid[i][j] = grid[i-1][n-1];
            else if (j > 0) grid[i][j] = grid[i][j-1];
        }
    }
    grid[0][0] = last;
}

วิธีที่ 2: Flatten + Modulo (แนะนำ O(mn))

vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();
    int total = m * n;
    k %= total;  // ลด k ให้อยู่ในช่วง
    
    vector<int> flat;
    flat.reserve(total);
    for (auto& row : grid) 
        for (int val : row) flat.push_back(val);
    
    // Rotate right k: ใหม่[i] = เก่า[(i - k + total) % total]
    vector<int> rotated(total);
    for (int i = 0; i < total; i++) {
        rotated[i] = flat[(i - k + total) % total];
    }
    
    // Reshape
    vector<vector<int>> result(m, vector<int>(n));
    for (int i = 0; i < total; i++) {
        result[i/n][i%n] = rotated[i];
    }
    return result;
}

โค้ด C++ ครบ (ใช้วิธี Simulate ตามโจทย์)

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

void printGrid(const vector<vector<int>>& g) {
    cout << "[";
    for (int i = 0; i < g.size(); i++) {
        cout << "[";
        for (int j = 0; j < g[i].size(); j++) {
            cout << g[i][j] << (j+1= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (j == 0 && i > 0) grid[i][j] = grid[i-1][n-1];
                else if (j > 0) grid[i][j] = grid[i][j-1];
            }
        }
        grid[0][0] = last;
    }
    
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& g, int k) {
        while (k--) shift(g);
        return g;
    }
};

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

Output

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

ความซับซ้อน

Input / Output

Input:  {{1,2,3},{4,5,6},{7,8,9}}, k=1
Output: [[9,1,2],[3,4,5],[6,7,8]]