[LeetCode] 885. Spiral Matrix III

https://leetcode.com/problems/spiral-matrix-iii/submissions/1348374879/

leetcode - Spiral Matrix III

문제 유형 : 행렬, 구현

문제 난이도 : Medium

 

문제

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.

 

당신은 rows x cols 크기의 행렬에서 오른쪽을 본 채로 셀 (rStart, cStart)부터 시작한다.

북서쪽 코너가 첫 행, 열이고, 남동쪽이 마지막 행, 열이다.

 

시계방향으로 나선을 그리며 행렬을 순회한다.

행렬의 바깥으로 나와도, 그냥 계속 돌면 된다.

 

행렬을 방문하는 좌표의 순서를 담아 반환하시오.

 

풀이

나선 회전을 할 때, 처음에는 우측을 바라보고 있다고 했다.

오른쪽 이동 -> 아래쪽 이동을 한 뒤, 뻗어야 하는 거리가 1 늘어난다.

왼쪽 이동 -> 위쪽 이동을 한 뒤, 뻗어야 하는 거리가 1 늘어난다.

나선 회전을 하면서, 현재 위치가 유효한 위치이면, 정답 배열에 {현재 행, 현재 열}을 뒤에 추가한다.

 

처음 위치를 방문처리하는 것을 잊지말자.

모든 칸을 다 방문했다면, 그만 멈춘다.

 

코드

C++

class Solution {
public:
    bool isInMatrix(int currRow, int currCol, int rows, int cols) {
        return currRow >= 0 && currRow < rows && currCol >= 0 && currCol < cols;
    }
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> ans;
        int leftBox = (rows * cols) - 1;
        int currRow = rStart, currCol = cStart;
        int moveRange = 1;
        ans.push_back({currRow, currCol});
        while(leftBox > 0) {
            // move Right
            for(int i = 0; i < moveRange; i++) {
                currCol++;
                if(isInMatrix(currRow, currCol, rows, cols)) {
                    ans.push_back({currRow, currCol});
                    if(--leftBox <= 0) return ans;
                }
            }

            // move Down
            for(int i = 0; i < moveRange; i++) {
                currRow++;
                if(isInMatrix(currRow, currCol, rows, cols)) {
                    ans.push_back({currRow, currCol});
                    if(--leftBox <= 0) return ans;
                }
            }

            moveRange++;

            // move Left
            for(int i = 0; i < moveRange; i++) {
                currCol--;
                if(isInMatrix(currRow, currCol, rows, cols)) {
                    ans.push_back({currRow, currCol});
                    if(--leftBox <= 0) return ans;
                }
            }

            // move Up
            for(int i = 0; i < moveRange; i++) {
                currRow--;
                if(isInMatrix(currRow, currCol, rows, cols)) {
                    ans.push_back({currRow, currCol});
                    if(--leftBox <= 0) return ans;
                }
            }
            
            moveRange++;
        }

        return ans;
    }
};