C++で2Dグリッドをシフトする方法【アルゴリズムと実装例】

m × n のサイズを持つ2次元グリッドと整数 k が与えられます。ここで、グリッドに対してシフト操作を k 回実行することを考えます。シフト操作の規則は以下のとおりです。

• grid[i][j] の要素は grid[i][j + 1] へ移動します

• 各行の末尾 grid[i][n – 1] の要素は、次の行の先頭 grid[i + 1][0] へ移動します

• 右下隅 grid[m – 1][n – 1] の要素は、左上隅 grid[0][0] へ移動します

たとえば、次のようなグリッドがあるとします。

これを1回シフトすると、出力は次のようになります。

この問題は、「グリッド全体を1マスずつ右方向にローテーションし、あふれ出した要素を左上に戻す」という処理だと考えると理解しやすくなります。

解法のアプローチ

この問題は、以下の手順に沿って解くことができます。

• シフト操作は行列を引数として受け取ります

• n := 行数、m := 列数とし、x := 右下の要素を一時的に退避します

• i を n – 1 から 0 まで降順にループします

  • j を m – 1 から 0 まで降順にループします

    • j = 0 かつ i > 0 の場合：G[i][j] := G[i – 1][m – 1]（前の行の末尾の要素を代入）

    • そうでなく j > 0 の場合：G[i][j] := G[i][j – 1]（左隣の要素を代入）

• G[0][0] := x（退避しておいた右下の要素を左上へ配置します）

• 続いて、以下の規則でシフト操作を呼び出します

• k が 0 になるまで繰り返します

  • グリッド G を1回シフトする

  • k を 1 減らす

• 最後にグリッド G を返します

C++による実装例

それでは、実際の実装を見てみましょう。以下のコードで動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] <<", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    void shift(vector<vector<int>>& grid){
        int n = grid.size();
        int m = grid[0].size();
        int x = grid[n-1][m-1];
        for(int i = n-1; i>=0; i--){
            for(int j = m-1;j>=0;j--){
                if(j == 0 && i>0){
                    grid[i][j] = grid[i-1][m-1];
                }
                else if(j>0){
                    grid[i][j] = grid[i][j-1];
                }
            }
        }
        grid[0][0] = x;
    }
    vector<vector<int>> shiftGrid(vector<vector<int>>& g, int k) {
        while(k--){
            shift(g);
        }
        return g;
    }
};
main(){
    Solution ob;
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    print_vector(ob.shiftGrid(mat, 1));
}

入力

{{1,2,3},{4,5,6},{7,8,9}}
1

出力

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

計算量と最適化のポイント

この実装では、1回のシフト操作に O(m × n) の時間がかかるため、全体の時間計算量は O(k × m × n) となります。その一方で、追加のメモリは不要であり、空間計算量は O(1) です。

また、覚えておくと便利な性質として、グリッドは m × n 回シフトすると元の状態に戻ります。したがって、処理前に k を k % (m × n) で置き換えることで、k が非常に大きい場合でも無駄な繰り返しを省略でき、効率を大幅に改善できます。