きれいな渦を出力(水平1022)

(ソース)https://www.acmicpc.net/problem/1022

📖 概要

上の図に示すように、1(0,0)の数字の座標から始め、渦のように徐々に進んでマップの問題を塗りつぶす必要があります.

💡 うずまきパターン

問題で与えられた渦モードは,右->上->左->下移動の繰り返しからなる.
したがって、(0,0)座標から右、上、左、下の順に移動してから右のモードに戻ればよく、指定された移動回数を全て特定の方向に移動すれば移動方向の変更が実現される.
移動回数は、最初(0,0)の座標から1回右に移動し、1回上に移動します.次に2を左に移動し、2を下に移動し、3を右に移動します.
繰り返しているうちによく観察してみると,左回りと右回りで移動する回数+1の法則が存在することが分かった.
そのため,対応するルールが追加され,右上左下モードが体現されている.

👓 詳細な実装方法

問題で与えられた渦巻きマップの座標範囲は-5000~5000であり、すべてのマップを2次元配列として表す場合はarray[1000][10000]を割り当てる必要がある.
アレイに約1億個のint型要素を保持する場合、約4億バイト=400 mbのメモリが使用されるため、メモリは128 mbを超えると予想されます.
したがって,1から1億まですべての渦巻き図を描き,入力要求に合致する範囲の数でなければpassを過去にし,その範囲の数だけを記憶させて論理的に行う.
(正確には、無限ループを回転させて渦を生成するとともに、これまでアレイに記憶されていた数を算出し、必要な数をすべて保存したままループを終了するようにコードを記述する)
また、個別に作成したマッピング(タイリング)のインデックスが、渦マップを表す座標と一致しないため、タイリングインデックス値を処理するプロセスが追加されました.また、最終出力時にその数字に基づいてスペース追加処理を行うために、値を格納したときに格納された最大桁数を記録している.

💻 コード#コード#

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int r1,c1,r2,c2;
    cin >> r1 >> c1 >> r2 >> c2;
    vector<vector<int>> resultMap(r2-r1+1, vector<int>(c2-c1+1));
    int totalCoorNum = (r2-r1+1) * (c2-c1+1);
    int currentNum = 0, currentRow= 0, currentCol = 0;
    int discovered = 0, pattern = 0;
    int level = 1;  // level == 현재 패턴의 이동횟수 레벨. 패턴 변동시 remainedMoveCnt가 level 값에 맞게 충전됨.
    int remainedMoveCnt = 1; // remainedMoveCnt == 해당 패턴으로 이동해야하는 횟수. 0이 될시 패턴(방향) 변경
    int space = 0;


    int direction [4][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}}; //우상좌하 순
    // 0,0 좌표부터 소용돌이를 그려가기 시작한다(무한루프로 돌림)
    // 루프를 돌면서 result로 반환해야하는 좌표를 지날때마다 resultMap에 좌표에 해당하는 값을 저장하고 discovered를 +1 증가시킨다. 발견해야하는 모든 좌표의 수에 discovered가 도달할 경우 루프를 종료시킨다.
    while(discovered != totalCoorNum) {
        currentNum++;
        if((r1 <= currentRow && currentRow <= r2) && (c1 <= currentCol && currentCol <= c2)) {
            discovered++;
            resultMap[currentRow-r1][currentCol-c1] = currentNum;
            int temp = currentNum / 10;
            int tempSpace = 0;
            while(temp != 0) {
                tempSpace++;
                temp /= 10;
            }
            if(tempSpace > space) space = tempSpace;
        }

        currentRow += direction[pattern][0];
        currentCol += direction[pattern][1];

        remainedMoveCnt--; //소용돌이 한칸 이동시키기
        if(remainedMoveCnt == 0) {
            pattern++;
            if(pattern == 4) {
                pattern = 0; //패턴 종료시 초기 패턴인 0으로 되돌리기
                level++;
            }
            if(pattern == 2) level++;
            remainedMoveCnt = level;
        }
    }

    for(int i = 0; i < r2 - r1 + 1; i++) {
        for(int j=0; j < c2 - c1 + 1; j++) {
            int temp = (*(resultMap.begin() + i))[j] / 10;
            int tempSpace = 0;
            while(temp != 0) {
                tempSpace++;
                temp /= 10;
            }

            for(int i = 0; i < space - tempSpace; i++) {
                cout << " ";
            }
            cout << (*(resultMap.begin() + i))[j];
            if(j != c2 - c1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}