C++のスパイラルマトリックスIII

R行とC列の2次元グリッドがあるとすると、東向きの（r0、c0）から開始します。ここで、グリッドの北西の角は最初の行と列にあり、グリッドの南東の角は最後の行と列にあります。このグリッドのすべての位置を訪問するために、時計回りのスパイラル形状で歩きます。グリッドの境界の外側にいるときは、グリッドの外側を歩き続けます（ただし、後でグリッドの境界に戻る場合があります）。グリッドの位置を表す座標のリストを、訪問した順序で見つける必要があります。したがって、グリッドが-

次に、矢印がパスになります。

これを解決するには、次の手順に従います-

• dirrを作成：=[[0,1]、[1,0]、[0、-1]、[-1,0]]

• 行列を作成しますret、len：=0、dir：=0

• （r0、c0）をretに挿入します

• retのサイズ

  • dir=0またはdir=2の場合、lenを1増やします

  • 0からlen– 1

    の範囲のiの場合

    • r0：=r0 + dirr [dir、0]、c0：=c0 + dirr [dir、1]

    • r0が0からRの範囲にあり、c0が0からCの範囲にある場合は、次の反復に進みます

    • （r0、c0）をretに挿入します

  • dir：=（dir + 1）mod 4

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > 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;
}
int dirr[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
class Solution {
   public:
   vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
      vector < vector <int> > ret;
      int len = 0;
      int dir = 0;
      ret.push_back({r0, c0});
      while(ret.size() < R * C){
         if(dir == 0 || dir == 2) len++;
         for(int i = 0; i < len; i++){
            r0 = r0 + dirr[dir][0];
            c0 = c0 + dirr[dir][1];
            if(r0 < 0 || c0 < 0 || c0 >= C || r0 >= R) continue;
            ret.push_back({r0, c0});
         }
         dir = (dir + 1) % 4;
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.spiralMatrixIII(5,5,1,3));
}

入力

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]]