सी++ में सर्पिल मैट्रिक्स III

मान लीजिए कि हमारे पास आर पंक्तियों और सी कॉलम के साथ एक 2 आयामी ग्रिड है, हम पूर्व की ओर (r0, c0) से शुरू करते हैं। यहां, ग्रिड का उत्तर-पश्चिम कोना पहली पंक्ति और स्तंभ पर है, और ग्रिड का दक्षिण-पूर्व कोना अंतिम पंक्ति और स्तंभ पर है। हम इस ग्रिड में हर स्थिति का दौरा करने के लिए एक दक्षिणावर्त सर्पिल आकार में चलेंगे। जब हम ग्रिड की सीमा के बाहर होते हैं, तो हम ग्रिड के बाहर अपना चलना जारी रखते हैं (लेकिन बाद में ग्रिड सीमा पर वापस आ सकते हैं।) हमें निर्देशांक की एक सूची ढूंढनी होगी जो ग्रिड की स्थिति का प्रतिनिधित्व करने वाले क्रम में उनका दौरा किया गया था। तो अगर ग्रिड की तरह है -

तब तीर पथ होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dirr बनाएं:=[[0,1],[1,0],[0,-1],[-1,0]]

• एक मैट्रिक्स रिट बनाएं, लेन:=0, डीआईआर:=0

• रिट में (r0, c0) डालें

• जबकि रिट का आकार

  • यदि dir =0 या dir =2 है, तो लेन को 1 से बढ़ाएँ

  • मैं के लिए 0 से लेन - 1 की सीमा में

    • r0 :=r0 + dirr[dir, 0], c0 :=c0 + dirr[dir, 1]

    • यदि r0 0 से R की सीमा में है, और c0 0 से C की सीमा में है, तो अगले पुनरावृत्ति के लिए जाएं

    • रिट में (r0, c0) डालें

  • डीआईआर:=(डीआईआर + 1) मॉड 4

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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