मान लीजिए हमारे पास R पंक्तियों और C स्तंभों वाला एक 2-आयामी ग्रिड है, हम (r0, c0) से शुरू करते हैं और पूर्व की ओर मुख किए होते हैं। यहां, ग्रिड का उत्तर-पश्चिम कोना पहली पंक्ति और स्तंभ पर है, और दक्षिण-पूर्व कोना अंतिम पंक्ति और स्तंभ पर है। हम इस ग्रिड में हर स्थिति को देखने के लिए दक्षिणावर्त सर्पिल आकार में चलेंगे। जब हम ग्रिड की सीमा के बाहर होते हैं, तो हम ग्रिड के बाहर चलना जारी रखते हैं (लेकिन बाद में ग्रिड सीमा पर वापस आ सकते हैं)। हमें ग्रिड की स्थितियों के निर्देशांकों की एक सूची खोजनी है जिस क्रम में वे देखे गए थे।
समाधान दृष्टिकोण
दिशा ऐरे dirr := [[0,1],[1,0],[0,-1],[-1,0]]
ret मैट्रिक्स, len := 0, dir := 0 बनाएं
(r0, c0) को ret में डालें
जब तक ret का आकार < R*C:
यदि dir = 0 या 2 तो len++
len चरणों के लिए: r0, c0 अपडेट करें, यदि ग्रिड में है तो ret में जोड़ें
dir = (dir+1)%4 अपडेट करें
ret लौटाएं
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;
}
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;
}
};
int main(){
Solution ob;
print_vector(ob.spiralMatrixIII(5,5,1,3));
return 0;
}
इनपुट
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]]
