[伯俊]#13460ビーズを脱出する

16717 ワード
白駿 ps C BFS データ構造 baekjoon テキストリンク

問題はここで確認できます.BaekJoon #13460. ビーズを脱出する

📌 POINT


  • スケートボードを傾けた時、赤珠「湾」は目的地に着きますか?

  • 10回の試みで成功したら、何回到着しますか?
    👉 移動+回数=BFSアルゴリズム

  • 注意事項
    -条件:赤と青は同じセルに配置できません.
    赤と青の球が同じ線上にあり、スクロールの結果位置が同じである場合は、後処理が必要です.
    -パスに宛先があるかどうかを確認する必要があります

    • 🚀 に答える


    Ready

  • Redでは、青色光球の位置情報が常に結合されます.可読性のためにも,位置情報を含む構造体を用意しておく.
    • struct pos{
    int x;
    int y;
    pos(int X, int Y) : x(X), y(Y) {}
};
  • 地図、碁盤等の場合は、1マス毎の状態を予め数字に変換して処理する.(多くの場合、文字列はもっと面倒です.)また、デジタル変換された状態では#defineが容易に見られます.
    • #define WALL -1
#define BLANK 0
#define HOLE 1

    GO


    1.基本的なBFSフレームワークを作成します。


    1.1. ゲームon関数は開始時にボールの位置を受け入れ,成功すれば試行回数を返し,10回以内に成功しなければ−1を返す.
    1.2. 日移動の結果、red、blueの位置情報ペアをキューに入れます.
    int game_on(pos start_red, pos start_blue){
    queue<pair<pos, pos>> q;
    q.push(make_pair(start_red, start_blue));

    int day = 1;
    bool hole_in = false;
    for(; day<=10; day++){
        int qsize = q.size();
        for(int i=0; i<qsize; i++){
            // tilt
            pos red = q.front().first;
            pos blue = q.front().second;
            q.pop();

            hole_in = tilt_board(red, blue, q);
            if(hole_in) return day;
        }
    }
    return -1;
}

    2.あちこち移動


    2.1. 移動結果はboolタイプで目的地に到着するかどうかを受け入れます.
    2.2. redとblueの両方が到着しなかったら、キューに入れて帰ります.
    bool tilt_board(pos &red, pos &blue, queue<pair<pos, pos>> &q){
    if(tilt_left(red, blue, q)) return true;
    if(tilt_right(red, blue, q)) return true;
    if(tilt_up(red, blue, q)) return true;
    if(tilt_down(red, blue, q)) return true;
    return false;
}

    3.傾斜の結果を保存


    上のコードに示すように、上下左右の関数がそれぞれ作成されています.合う気がしたけど...まず知らないで、知っている方法で書きました.
    3.1. 移動と到着調査
    is_red_in = move(next_red, move_dir[0]);
is_blue_in = move(next_blue, move_dir[0]);
    3.2. 同じ線上に2つの球があるかどうか>移動後に重なるかどうか
    // 같은 라인 상에 존재하는지
// right (방향에 따라 코드 차이 발생)
if(red.x == blue.x){
    if(next_red.y == next_blue.y){
        if(red.y < blue.y) next_red.y--;
        else next_blue.y--;
    }
}
    3.3. 到着するかどうかを返す
    if(is_red_in && !is_blue_in) return true;
else if(!is_blue_in){
    q.push(make_pair(next_red, next_blue));
}
return false

    4.スライドを傾けたときにボールを動かす

    move_dirアレイコードをよりスムーズに
    // right, left, down, up
int move_dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool move(pos &ball, int dir[]){
    while(true){
        pos next = ball;
        next.x += dir[0];
        next.y += dir[1];
        if(board[next.x][next.y] == HOLE){
            return true;
        }
        else if(board[next.x][next.y] == BLANK){
            ball = next;
        }
        else {  // WALL
            return false;
        }
    }
}

    ためらう


    三星のソフトウェア能力試験は約1週間前から脱気を始めた.予想外のアルゴリズムが大幅に外れることはないので,毎日学習や整理解答を行うことが役に立つかもしれないという後記が多い.今日から毎日1本の問題を出します!
    [アルゴリズム]バイナリナビゲーション
    方法の3つの練習問題