[アルゴリズム解解析]BOJ 15685竜曲線

今日の質問はBOJ 15685竜曲線です!
シミュレーション問題ですが、規則性を見つけるのは難しいですが、このタイプはまた初めてのようなので、勉強が深い問題です!いくらでも出てくるから、時間が経ったらまた解いてみなきゃ!

BOJ 15685竜曲線

ドラッグカーブは、2 D座標平面で定義された3つのアトリビュートで構成されます.座標平面のx軸は→方向、y軸は↓方向です.

始点2.開始方向第

世代
0代目龍曲線は、下図のように長さ1の線分です.下図は(0,0)から始まり、開始方向は右側の0代目龍曲線です.

第1世代龍曲線は、第0世代龍曲線を終点として時計回りに90度回転し、第0世代龍曲線の終点に貼り付けられます.終点とは、始点から線分に沿って移動したときに最も遠い点です.
第2世代竜巻も第1世代を作る方法で作ることができます.(青い線分は新しく追加した線分を表します)

3代目龍曲線も2代目龍曲線で作ることができます.下図は3代目ドラゴンカーブです.
すなわち、K(K>1)世代龍曲線は、K-1世代龍曲線を端点を基準に時計回りに90度回転させ、端点に貼り付ける.
サイズは100×100人の人格にはN本の龍曲線がある.サイズ1×正方形の4つの頂点が曲線の一部をドラッグする正方形の個数であることを求めるプログラムを作成します.メッシュの座標は(x,y)と表され、0≦x≦100、0≦y≦100万の有効座標である.

にゅうしゅつりょく

私の答え

まず問題そのものを理解するのに少し時間がかかりました.ははは
何の話だ...作りながら解くのですが、
実际、私の头の中ですべての情况の数量を掌握することができなくて、きっとどんな规则があるでしょう~だから私は规则を探して、、、、絵、cos、tan、いろいろとすべて书いてみて、しかし最后に私は探し出せません^^圭...勅.姓...ううう
点移動の法則性を見つけようとした.(x 1,y 1)->(x 2,y 2)の点の変化には変化量の法則があると思いますが、答えはそうではありません!
複数の座標の変化ではなく、座標は1つの起点だけを基準にして、方向の変化の中で、規則性を把握することが核心です!

最初に与えられた方向番号を0とします.
始点(0,0)から0方向(->)に移動したところが終点(1,0)となり、0代目線分が完成します.
その後、線分を終点(1,0)を基準に時計回りに90度回転させ、接触した箇所が新たな終点(1,-1)となり、このとき終点の移動方向(1,0)->(1,-1)が方向1(↑)と一致する.
見どころだけが移動する方向なら、2代目線分の方向変換順は0(→)-1(↑)-2(←)-1(↑)です.

0世代:024579182

第1世代:0-1

第2世代:0-1-2-1

このとき、第2世代が追加した最後の2つの線分の方向(2-1)から、第1世代線分(0-1)は逆の順に1を加えた値であることがわかる.
第2世代:0-1-2(1+1)-1(0+1).
つまり、k世代に新しく追加された線分の方向は、k-1世代の線分の方向に1を逆順に追加します!
この法則性を見つけることがこの問題の核心だ!!
規則性が見つかった後、コードで実現するしかありません.

線分の最後の座標<pair<int, int>>> last

記録

線分方向の配列vector<int> directions

k世代で新規線分を追加する場合は、先に記録した方向に応じて方向を決定します.size()と同じ新しい方向を追加し、map[last.first][last.second]=1を変更しながら、追加した方向に最後の座標を移動します.

すべての線分を描いた後、図中の隣接する4格子がすべて1であればcount

コード#コード#

#include <iostream>
#include <vector>

// BOJ 15685 드레곤 커브, simulation
using namespace std;

int dy[4] = {0,-1,0,1};
int dx[4] = {1,0,-1,0};;

vector<vector<int>> map(101, vector<int>(101, 0));

void drawDragonCurve(int x, int y, int dir, int gen){
    vector<int> directions;
    directions.push_back(dir);

    pair<int, int> last = make_pair(y+dy[dir], x+dx[dir]);
    map[y][x] = 1;
    map[last.first][last.second] = 1;

    while (gen > 0){
        int size = directions.size();

        for (int i = size-1; i >= 0; i--) {  // 새로운 방향 추가
            directions.push_back((directions[i]+1)%4);
        }

        for (int i = size; i < 2*size; ++i) {  // 추가된 방향 만큼 선분 연장 
            last.first += dy[directions[i]];
            last.second += dx[directions[i]];
            map[last.first][last.second] = 1;
        }
        gen--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, x, y, dir, gen;
    cin>>N;

    for (int i = 0; i < N; ++i) {
        cin>>x>>y>>dir>>gen;
        drawDragonCurve(x, y, dir, gen);
    }

    int box = 0;
    for (int i = 0; i < 100; ++i) {
        for (int j = 0; j < 100; ++j) {
            if (map[i][j]==1){
                if (map[i][j+1]==1 && map[i+1][j] && map[i+1][j+1]) box++;
            }
        }
    }

    cout<<box;

    return 0;
}

[BOJ 15685]ドラゴンカーブ