R 행과 C 열이 있는 2차원 그리드가 있다고 가정하고 동쪽을 향한 (r0, c0)에서 시작합니다. 여기서 그리드의 북서쪽 모서리는 첫 번째 행과 열에 있고 그리드의 남동쪽 모서리는 마지막 행과 열에 있습니다. 우리는 이 그리드의 모든 위치를 방문하기 위해 시계 방향 나선 모양으로 걸을 것입니다. 그리드 경계 외부에 있을 때 그리드 외부로 계속 걸어갑니다(그러나 나중에 그리드 경계로 돌아올 수 있음). 방문한 순서대로 그리드의 위치를 나타내는 좌표 목록을 찾아야 합니다. 따라서 그리드가 다음과 같은 경우 -
그러면 화살표가 경로가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
디렉토리 생성 :=[[0,1],[1,0],[0,-1],[-1,0]]
-
행렬 생성 ret, len :=0, dir :=0
-
ret에 (r0, c0) 삽입
-
동안 크기 ret
-
dir =0 또는 dir =2이면 len을 1 증가시킵니다.
-
범위 0에서 len – 1에 있는 i의 경우
-
r0 :=r0 + 디렉토리[dir, 0], c0 :=c0 + 디렉토리[dir, 1]
-
r0이 0~R 범위에 있고 c0이 0~C 범위이면 다음 반복으로 이동합니다.
-
ret에 (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]]