[ACM] 시계 방향 으로 행렬 인쇄

문제 설명: 행렬 을 입력 하고 외 향 에서 시계 방향 으로 순서대로 모든 숫자 를 출력 한다. 예 를 들 어 다음 과 같은 행렬 을 입력 하면 1, 2, 3, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
알고리즘 설명: (x, y) 원 조 를 현재 인쇄 요소 의 지침 으로 하고 현재 위치 에 - 1, 0, 1 을 더 하면 각각 x, y 좌표 가 후퇴 하고 변 하지 않 으 며 전진 하 는 것 을 나타 낸다.행렬 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 15, 16.
현재 위치 가 (0, 0) 이면 1 을 인쇄 합 니 다.시계 방향 으로 인쇄 할 때 다음 위치 로 이동 하면 x + 1, y + 0 이 므 로 (1, 0), 즉 인쇄 2 입 니 다.다시 아래로, (2, 0), 인쇄 3;...마지막 요 소 는 (1, 2) 입 니 다. 인쇄 10. 먼저 한 줄 의 단일 열 인지 확인 합 니 다. 만약 에 하나의 for 순환 만 하면 해결 할 수 있 습 니 다. 그렇지 않 으 면 다음 단계 에 들 어 갑 니 다. 좌표 (0, 0) 부터 x 는 순서대로 증가 하고 y 는 변 하지 않 습 니 다. 또한 x, y 의 최대 최소 치 x 를 기록 합 니 다.min,x_max 와 ymin.y_max, 그리고 좌 표를 이동 하기 시작 합 니 다.경계 위치 (x max, y min) 로 이동 할 때 첫 줄 이 인쇄 되 었 음 을 나타 내 므 로 xmin + = 1, 동시에 x 는 변 하지 않 고 y 는 아래로 증가 합 니 다.경계 위치 (x max, y max) 로 이동 할 때 마지막 열 이 인쇄 되 었 음 을 나타 내 므 로 ymax - = 1, 동시에 y 는 변 하지 않 고 x 는 뒤로 점점 줄어든다.경계 위치 (x min, y max) 로 이동 할 때 마지막 줄 이 인쇄 되 었 음 을 나타 내 므 로 xmax - = 1, 동시에 x 는 변 하지 않 고 y 는 위로 점점 줄어든다.경계 위치 (x min, y min) 로 이동 할 때 첫 번 째 열 이 인쇄 되 었 음 을 나타 내 므 로 ymin - = 1, 동시에 y 는 변 하지 않 을 것 입 니 다. x 는 앞으로 점점 증가 할 것 입 니 다. 이 단 계 는 시계 방향 으로 한 바퀴 돌 고 나 서 야 검 사 를 할 수 있 습 니 다.인 코딩 을 할 때 매번 min 과 max 의 변 화 는 다음 경계 점 으로 옮 겨 야 진행 할 수 있 습 니 다. 그렇지 않 으 면 순환 에 빠 져 배열 이 넘 칠 수 있 습 니 다 (구체 적 으로 코드 를 볼 수 있 습 니 다).
코드 는 다음 과 같 습 니 다:
class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> results;
        if (matrix.size() == 0) {
            return results;
        }

        int x = 0; 
        int y = 0; //       

        int xf = 0;
        int yf = 1;//xf yf             ,-1   ,0  ,1  

        int rows = matrix.size()-1;     // 
        int cols = matrix.at(0).size()-1; // 
        //      
        if (rows == 0) {
            for (int i = 0; i <= cols; i++) {
                results.push_back(matrix.at(0).at(i));
            }
            return results;
        }
        //      
        if (cols == 0) {
            for (int i = 0; i <= rows; i++) {
                results.push_back(matrix.at(i).at(0));
            }
            return results;
        }

        int x_start = 0;
        int y_start = 0;

        int x_end = rows;
        int y_end = cols;

        bool isFirst = true;

        int size = (rows+1)*(cols+1);   //    
        while (results.size() < size) {
            results.push_back(matrix[x][y]);    //      
            x += xf;                            //     
            y += yf;                            //     
            //                
            if (x == x_start && y == y_end) {
                xf = 1;
                yf = 0;
                if (!isFirst) {
                    y_start += 1;
                }
            }
            if (x == x_end && y == y_end) {
                xf = 0;
                yf = -1;
                x_start += 1;

            }
            if (x == x_end && y == y_start) {
                xf = -1;
                yf = 0;
                y_end -= 1;

            }
            if (x == x_start && y == y_start) {
                xf = 0;
                yf = 1;
                x_end -= 1;
                isFirst = false;
            }
        }
        return results;
    }
};

테스트 코드:
int main() {

    vector<vector<int> > matrix;
    int x = 1;
    for (int i = 0; i < 4; i++) {
        vector<int> tmp;
        for (int j = 0; j < 1; j++) {
            tmp.push_back(x++);
        }
        matrix.push_back(tmp);
    }

    Solution s;

    vector<int> re = s.printMatrix(matrix);

    for (int i = 0; i < re.size(); i++) {
        cout << re[i] << " ";
    }
}

좋은 웹페이지 즐겨찾기