AHC033　参加記録~茶コーダーでも水パフォを取れる!!

#include <bits/stdc++.h>
using namespace std;

class table_class {
    public:
    /*初期化や入力受け取り*/
    table_class(): out_cnt(0) {
        table.assign(n, vector<int>(n, -1));
        next_list.assign(n, queue<int>());
        now_exist_list.assign(n, set<int>());
        next_pop_list.assign(n, set<int>());
        for (int i = 0; i < n * n; i++) {
            next_pop_list[i / n].insert(i);
        }
        small_crane_pos.assign(n, {-1, -1});
        big_crane_has_container = false;
    }

    void set_next_container(int i, int next) {
        next_list[i].push(next);
    }

    /*ターンごとの処理(搬入出の処理など)*/
    //搬入
    void push_next_container() {
        for (int i = 0; i < n; i++) {
            if (exist_container(i, 0)) continue;
            if (next_list[i].empty()) continue;
            int next = next_list[i].front();
            next_list[i].pop();
            table[i][0] = next;

            now_exist_list[next / n].insert(next);
        }
    }
    //搬出
    void pop_container() {
        for (int i = 0; i < n; i++) {
            if (exist_container(i, n - 1)) {
                out_cnt++;
                int erace_num = table[i][n - 1];
                now_exist_list[erace_num / n].erase(erace_num);
                next_pop_list[erace_num / n].erase(erace_num);
                table[i][n - 1] = -1;
            }
        }
    }
    //終了判定
    bool done_all_container() {
        if (out_cnt == n * n) return true;
        else return false;
    }

    /*コンテナの位置、配置、消去*/
    /// @brief コンテナがおかれているか
    bool exist_container(int i, int j) {
        if (table[i][j] != -1) return true;
        else return false;
    }

    int get_container_num(int i, int j) {
        return table[i][j];
    }

    void set_cotainer(int i, int j, int num) {
        table[i][j] = num;
    }

    void erace_container(int i, int j) {
        table[i][j] = -1;
    }

    /*クレーンの座標管理*/
    /*大クレーン*/
    /// @brief　大クレーンの座標を取得
    pair<int, int> get_big_crane_pos() {
        return big_crane_pos;
    }

    /// @brief 大クレーンの座標を設定
    void set_big_crane_pos(int pos_x, int pos_y) {
        big_crane_pos = {pos_x, pos_y};
    }

    /// @brief 大クレーンがコンテナを持っているかどうか
    bool get_big_crane_has_container() {
        return big_crane_has_container;
    }

    /// @brief 大クレーンのコンテナ所持フラグのセッター
    void set_big_crane_has_container(bool flag) {
        big_crane_has_container = flag;
    }

    /*小クレーン*/
    /// @brief pos_x行目の搬出口に、小クレーンが待機しているか? 
    bool exist_out_place_crane(int pos_x) {
        if (out_place_crane.count(pos_x)) return true;
        else return false;
    }

    /// @brief  待機している小クレーンの位置(行)を教える
    void set_out_place_crane(int pos_x) {
        out_place_crane.insert(pos_x);
    }

    /// @brief 爆破されて消失したクレーンを削除する
    void erace_out_place_crane(int pos_x) {
        out_place_crane.erase(pos_x);
    }

    /// @brief 小クレーンの座標をまとめて返す(0番目は存在しないので常に-1,-1を返す)
    vector<pair<int, int> > get_small_cranes_pos() {
        return small_crane_pos;
    }

    /// @brief 小クレーンの位置を設定する
    void set_small_crane_pos(int crane_num, int pos_x, int pos_y) {
        small_crane_pos[crane_num] = {pos_x, pos_y};
    }

    /// @brief 小クレーンを削除時は、座標を-1,-1(存在しない)に設定する
    void erace_small_crane_pos(int crane_num) {
        small_crane_pos[crane_num] = {-1, -1};
    }

    /*次に選ぶべきものを返すシリーズ*/
    //最も早く、キューから次に搬出できるものがでてくる搬入口の番号[i]を返す
    int get_next_ones_que(int pos_x) {
        int que_num = -1;
        //十分大きい値
        int max = 100;
        int dist_x = 100;
        for (int i = 0; i < n; i++) {
            if (next_list[i].empty()) continue;
            queue<int> q = next_list[i];
            int cnt = 0;
            while (!q.empty()) {
                cnt++;
                int top = q.front();
                q.pop();
                if (can_pop(top)) break;
            }
            if (cnt < max) {
                que_num = i;
                max = cnt;
                dist_x = abs(i - pos_x);
            }
            else if (cnt == max) {
                //より近い搬入口を選ぶ
                if (abs(i - pos_x) < dist_x) {
                    que_num = i;
                    max = cnt;
                    dist_x = abs(i - pos_x);
                }
            }
        }
        return que_num;
    }

    /// @brief 一つでも空きマスが存在するか
    bool exist_empty_mass() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (exist_container(i, j) == false) return true;
            }
        }
        return false;
    }

    /*排出に関わる判定*/
    //num番のコンテナを今搬出するべきかを返す
    bool can_pop(int num) {
        for (int i = 0; i < n; i++) {
            if (next_pop_list[i].empty()) continue;
            if (*next_pop_list[i].begin() == num) return true;
        }
        return false;
    }

    private:
    const int n = 5;
    //搬出したコンテナ数
    int out_cnt;
    //実際の表、-1はコンテナが存在しないことを意味する
    vector<vector<int> > table;

    /*搬入出系メンバ*/
    //搬入予定
    vector<queue<int> > next_list;
    //現在の盤面で、i番目の搬出口から出したいものいれ
    vector<set<int> > now_exist_list;
    //[i]番目の搬出口から次に出したいものを取得するためのset
    vector<set<int> > next_pop_list;

    /*クレーン系メンバ*/
    bool big_crane_has_container;
    //大クレーンの座標
    pair<int, int> big_crane_pos;
    //setにxが含まれていれば、[x]行目の搬出口には小クレーンが待機している
    set<int> out_place_crane;
    //小クレーンが存在する座標
    vector<pair<int, int> > small_crane_pos;
};

class crane {
    public:
    crane() {}
    crane(int x, int y) {
        n = 5;
        pos_x = x;
        pos_y = y;
        goal_x = -1;
        goal_y = -1;
        container_num = -1;
    }

    virtual void update_action(table_class &table) {cout << "set_in_child_class!!";}

    string get_actions_string() {return actions;}

    protected:
    int n;
    //行動の手順
    string actions;
    //クレーンの座標(縦(iがx軸となっている点に注意))
    int pos_x, pos_y;
    //クレーンが今から移動したい場所(目的地の座標)
    int goal_x, goal_y;
    //現在、クレーンが持っているコンテナの番号(-1は持っていない)
    int container_num;

    void up_container(table_class &table) {
        container_num = table.get_container_num(pos_x, pos_y);
        if (container_num == -1) {
            do_nothing();
            return;
        }
        table.erace_container(pos_x, pos_y);
        actions += 'P';
    }

    void down_container(table_class &table) {
        table.set_cotainer(pos_x, pos_y, container_num);
        container_num = -1;
        actions += 'Q';
    }

    virtual void move(table_class &table) {cout << "set_in_child_class!!";};

    void do_nothing() {
        actions += '.';
    }

    void set_goal(int x, int y) {
        goal_x = x;
        goal_y = y;
    }

    void arrived(table_class &table) {
        //コンテナなし
        if (container_num == -1) {
            //コンテナを上げる
            up_container(table);
        }
        //コンテナあり
        else if (container_num != -1) {
            //コンテナを降ろす
            down_container(table);
        }
        goal_x = -1;
        goal_y = -1;
    }
};

//大きい方のクレーンクラス
class big_crane : public crane {
    public:
    big_crane() {}
    big_crane(table_class table, int x, int y) : crane(x, y) {
        table.set_big_crane_pos(x, y);
    }

    void update_action(table_class &table) override {
        bool is_setted_goal = goal_x != -1 && goal_y != -1;
        //目的地なし(この処理はターン消費なしで可能)
        //ゴール地点に移動したときに、小クレーンが大クレーンより左にある場合は配置してはいけない
        if (container_num != -1 && table.exist_out_place_crane(pos_x) && pos_x == goal_x && pos_y == goal_y &&
        table.get_small_cranes_pos()[pos_x].second < pos_y) {
            crane_avoid_move(table);
            return;
        }
        //コンテナなし
        if (container_num == -1) {
            pair<int, int> p = search_can_pop_pos(table, pos_x, pos_y);
            //今、搬出口に運べるコンテナが見つかった場合->目的地:{そのコンテナの座標,適切な搬入口}の近いほう
            if (p.first != -1 && p.second != -1) {
                int container_dist = abs(pos_x - p.first) + abs(pos_y - p.second);
                int next_que = table.get_next_ones_que(pos_x);
                //適切な搬入口
                if (next_que != -1 && (abs(pos_x - next_que) + abs(pos_y - 0)) <= container_dist && table.exist_empty_mass()) {
                    push_container_operation(table);
                }
                else {
                    //搬出できるコンテナ
                    set_goal(p.first, p.second);
                }
            }
            //今、表には搬出口に運びたいコンテナがないので搬入する->目的地:搬入口の邪魔なコンテナ
            else {
                push_container_operation(table);
            }
        }
        //コンテナあり
        else if (container_num != -1 && is_setted_goal == false) {
            //搬出しても良い場合
            if (table.can_pop(container_num)) {
                goal_x = container_num / n;
                if (table.exist_out_place_crane(goal_x)) {
                    //搬出口に小クレーンが待機しているかつ、搬出口の左マスが空マス
                    goal_y = ret_leftest_pos(table, goal_x, container_num);
                }
                //そうでなければ、大クレーンで搬出口に降ろしに行く
                else goal_y = n - 1;
            }
            //今、搬出するべきではない場合(なるべく理想の仮置き場を選ぶ)
            else {
                //第一希望
                int ideal_x = container_num / n;
                int ideal_y = n - 2 - (container_num % n);
                //第二希望(同じ行のn - 2より左側)
                pair<int, int> next_ideal = {-1, -1};
                for (int i = n - 3; i >= 0; i--) {
                    if (table.exist_container(ideal_x, i) == false) {
                        next_ideal = {ideal_x, i};
                    }
                }
                //第三希望(小クレーンのない、0行目のn - 2まで)
                pair<int, int> third_ideal = {-1, -1};
                for (int i = n - 2; i >= 0; i--) {
                    if (table.exist_container(0, i) == false) {
                        third_ideal = {0, i};
                    }
                }
                //第四希望(同じ行のn - 2があればそこ、なければ他のn - 2)
                pair<int, int> fourth_ideal = {-1, -1};
                for (int i = 0; i < n; i++) {
                    if (table.exist_container(i, n - 2) == false) {
                        fourth_ideal = {i, n - 2};
                    }
                }
                if (table.exist_container(ideal_x, n - 2) == false) {
                    fourth_ideal = {ideal_x, n - 2};
                }
                
               //理想の仮置き場が空いている場合
                if (ideal_y != -1 && table.exist_container(ideal_x, ideal_y) == false) {
                    goal_x = ideal_x;
                    goal_y = ideal_y;
                }
                //二番目の理想(同じ行のn - 2より左側)
                else if (next_ideal.first != -1 && next_ideal.second != -1) {
                    goal_x = next_ideal.first;
                    goal_y = next_ideal.second;
                }
                //三番目の理想
                else if (third_ideal.first != -1 && third_ideal.second != -1) {
                    goal_x = third_ideal.first;
                    goal_y = third_ideal.second;
                }
                //四番目の理想
                else if (fourth_ideal.first != -1 && fourth_ideal.second != -1) {
                    goal_x = fourth_ideal.first;
                    goal_y = fourth_ideal.second;
                }
                //最悪ケースだと、順番を守れなくなることもある
                else {
                    goal_x = ideal_x;
                    goal_y = n - 1;
                }
            }
        }

        //目的地に到着
        if (pos_x == goal_x && pos_y == goal_y) {
            int tmp_container = table.get_container_num(pos_x, pos_y);
            bool right_crane = false;
            for (auto x : table.get_small_cranes_pos()) {
                if (pos_y != 0) continue;
                if (pos_x == x.first && pos_y == x.second) right_crane = true;
            }
            if (table.exist_out_place_crane(pos_x) && tmp_container / n == pos_x && ret_leftest_pos(table, tmp_container / n, tmp_container) == pos_y
                && ret_leftest_pos(table, tmp_container / n, tmp_container) != -1 && right_crane) {
                //ゴール処理しない(arrivedを実行しないで、適当な場所へ向かうように書き換える)
                set_goal(rand() % (n - 1), 0);
            }
            else {
                arrived(table);
            }
            //コンテナを持っていればtrueが渡される
            table.set_big_crane_has_container(container_num != -1);
            return;
        }

        //目的地あり(コンテナの有無は問わない) && 未到着
        if (pos_x != goal_x || pos_y != goal_y) {
            move(table);
            return;
        }
    }
    protected:
    /*移動処理*/
    void move(table_class &table) override {
        //搬出口では、先に横移動を行わないと衝突する
        if (pos_y == n - 1) {
            if (move_left(table)) return;
            if (move_right(table)) return;
        }
        //iの軸での移動
        if (move_up(table)) return;
        if (move_down(table)) return;
        //jの軸での移動
        if (move_left(table)) return;
        if (move_right(table)) return;
    }

    /*各移動について、移動先に小クレーンが無ければ移動、あればdo_nothing()が実行される*/
    bool move_left(table_class &table) {
        if (goal_y == pos_y) return false;
        if (goal_y < pos_y) {
            if (check_move_to(table, pos_x, pos_y - 1) == false) {
                crane_avoid_move(table);
                return true;
            }
            pos_y--;
            actions += 'L';
            table.set_big_crane_pos(pos_x, pos_y);
            return true;
        }
        return false;
    }

    bool move_right(table_class &table) {
        if (goal_y == pos_y) return false;
        if (goal_y > pos_y) {
            if (check_move_to(table, pos_x, pos_y+ 1) == false) {
                crane_avoid_move(table);
                return true;
            }
            pos_y++;
            actions += 'R';
            table.set_big_crane_pos(pos_x, pos_y);
            return true;
        }
        return false;
    }

    bool move_up(table_class &table) {
        if (goal_x == pos_x) return false;
        if (goal_x < pos_x) {
            if (check_move_to(table, pos_x - 1, pos_y) == false) {
                do_nothing();
                return true;
            }
            pos_x--;
            actions += 'U';
            table.set_big_crane_pos(pos_x, pos_y);
            return true;
        }
        return false;
    }

    bool move_down(table_class &table) {
        if (goal_x == pos_x) return false;
        if (goal_x > pos_x) {
            if (check_move_to(table, pos_x + 1, pos_y) == false) {
                do_nothing();
                return true;
            }
            pos_x++;
            actions += 'D';
            table.set_big_crane_pos(pos_x, pos_y);
            return true;
        }
        return false;
    }

    /// @brief 移動先に小クレーンがなければtrueを返す
    bool check_move_to(table_class &table, int next_x, int next_y) {
        for (auto &tmp : table.get_small_cranes_pos()) {
            if (next_x == tmp.first && next_y == tmp.second) return false;
        }
        return true;
    }

    void crane_avoid_move(table_class &table) {
        //上下どちらかに抜けれる場合
        if (pos_x - 1 >= 0) {
            if (check_move_to(table, pos_x - 1, pos_y)) {
                pos_x--;
                actions += 'U';
                table.set_big_crane_pos(pos_x, pos_y);
                return;
            }
        }
        if (pos_x + 1 < n) {
            if (check_move_to(table, pos_x + 1, pos_y)) {
                pos_x++;
                actions += 'D';
                table.set_big_crane_pos(pos_x, pos_y);
                return;
            }
        }
        //抜け道なしの場合
        do_nothing();
        return;
    }

    /*目的地の設定*/
    /// @brief 適切な搬入口を目的地に設定する
    void push_container_operation(table_class &table) {
        //適切な搬入口を取得
        int que_num = table.get_next_ones_que(pos_x);
        //大クレーンが今すべきことがない場合
        //todo:とりあえず、ランダムに動いてもらう
        if (que_num == -1) {
            set_goal(rand() % (n - 1), rand() % (n - 1));
            return;
        }
        //目的地を設定
        set_goal(que_num, 0);
        return;
    }

    //表にすでにある中から、搬出してもよいコンテナの位置を返す(ない場合は-1, -1を返す)
    pair<int, int> search_can_pop_pos(table_class &table, int pos_x, int pos_y) {
        int dist = 100;
        pair<int, int> pos = {-1, -1};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                int tmp_container = table.get_container_num(i, j);
                if (table.exist_out_place_crane(i) && tmp_container / n == i && ret_leftest_pos(table, tmp_container / n, tmp_container) == j) continue;
                if (table.can_pop(table.get_container_num(i, j))) {
                    //なるべく現在地から近い場所を運ぶ
                    int tmp_dist = abs(pos_x - i) + abs(pos_y - j);
                    if (tmp_dist < dist) {
                      pos = {i, j};
                      dist = tmp_dist;
                    }
                }
            }
        }
        return pos;
    }

    ///目的地をy座標で小クレーンが取りにこれる最も左を設定
    int ret_leftest_pos(table_class &table, int arg_goal_x, int arg_container) {
        if (table.can_pop(arg_container) == false) {
            return -1;
        }
        int ans = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            int tmp_container = table.get_container_num(arg_goal_x, i);
            if (tmp_container != -1 && tmp_container != arg_container) break;
            ans = i;
        }
        //遠ざかるのは嫌なのでなるべく近いほうを探してみる
        if (ans < pos_y) {
            int dist = 100;
            for (int i = n - 2; i >= 0; i--) {
                int tmp_container = table.get_container_num(arg_goal_x, i);
                if (tmp_container != -1 && tmp_container != arg_container) break;
                if (abs(pos_y - i) < dist) {
                    ans = i;
                    dist = abs(pos_y - i);
                }
            }
        }
        return ans;
    }
};

class small_crane : public crane {
    public:
    small_crane() {};
    small_crane(int x, int y, table_class &table) : crane(x, y) {
        is_broken = false;
        table.set_out_place_crane(x);
        table.set_small_crane_pos(pos_x, x, y);
    };

    void update_action(table_class &table) override {
        //爆破後は操作しない
        if (is_broken) return;

        //解体判定(とりあえず、搬出口の左側に関係ないコンテナが来たら自爆させる)
        {
            int left_container = table.get_container_num(pos_x, n - 2);
            //空きマスじゃないかつ、(担当のコンテナでない、又は現在の対象でない場合)
            if (left_container != -1 && (left_container / n != pos_x || table.can_pop(left_container) == false)) {
               pair<int, int> big_c_pos = table.get_big_crane_pos();
               if (pos_y == n - 1 && big_c_pos.first == pos_x && big_c_pos.second == pos_y - 1 && table.get_big_crane_has_container()) {
                   if (container_num == -1) bomb(table);
                   return;
               }
            }
        }

        //コンテナなし
        if (container_num == -1) {
            int left_container_y = left_container_exist(table, pos_x, pos_y);
            //左側に運べそうな担当のコンテナなし
            if (left_container_y == -1) {
                //すでに搬出口で待機中
                if (pos_y == n - 1) {
                    /// @bug ちょっとあやしい...(ゴール設定の初期化のためなのだが...)
                    set_goal(pos_x, n - 1);
                    /// @attention ここだけはターン消費あり
                    do_nothing();
                    return;
                }
                //搬出口以外なら、搬出口へ向かう
                set_goal(pos_x, n - 1);
            }
            //運べそうなコンテナあり 
            else {
                //そのコンテナの位置を目指してもらう。
                set_goal(pos_x, left_container_y);
            }
        }
        //コンテナあり
        else {
            //搬出口へ向かう
            set_goal(pos_x, n - 1);
        }

        //目的地あり(コンテナの有無は問わない) && 未到着
        if (pos_y != goal_y) {
            move(table);
            return;
        }

        //目的地に到着
        if (pos_x == goal_x && pos_y == goal_y) {
            arrived(table);
        }
    }

    protected:
    bool is_broken;

    void move(table_class &table) override {
        //jの軸での移動しか行わない
        if (goal_y != pos_y) {
            if (goal_y < pos_y) {
                if (check_move_to(table, pos_x, pos_y - 1) == false) {
                    do_nothing();
                    return;
                }
                pos_y--;
                actions += 'L';
                table.set_small_crane_pos(pos_x, pos_x, pos_y);
                return;
            }
            if (goal_y > pos_y) {
                if (check_move_to(table, pos_x, pos_y + 1) == false) {
                    do_nothing();
                    return;
                }
                pos_y++;
                actions += 'R';
                table.set_small_crane_pos(pos_x, pos_x, pos_y);
                return;
            }
        }
    }

    /// @brief 移動先に大クレーンや、コンテナがなければtrueを返す
    bool check_move_to(table_class &table, int next_x, int next_y) {
        pair<int, int> p = table.get_big_crane_pos();
        if (next_x == p.first && next_y == p.second) return false;
        if (table.exist_container(next_x, next_y) && next_y != goal_y && container_num != -1) return false;
        return true;
    }

    /// @brief (そのマスを含む)それより左に、現在搬出可能なコンテナがあるか?
    int left_container_exist(table_class &table, int x, int y) {
        for (int i = y; i >= 0; i--) {
            if (table.get_container_num(x, i) == -1) continue;
            //このコンテナの希望の搬出口ではない場合
            if (table.get_container_num(x, i) / n != x) return -1;
            //発見
            if (table.can_pop(table.get_container_num(x, i))) return i;
            //搬出口はあっているが、順番違いの場合
            else return -1;
        }
       return -1;
    }

    void bomb(table_class &table) {
        actions += 'B';
        table.erace_out_place_crane(pos_x);
        table.erace_small_crane_pos(pos_x);
        is_broken = true;
    }
};

class ahc_033 {
    public:
    ahc_033(const table_class t) 
    :table(t) {
        table.push_next_container();
        big_c = big_crane(table, 0, 0);
        smalls = {small_crane(1, 0, table), small_crane(2, 0, table), small_crane(3, 0, table), small_crane(4, 0, table)};
    }

    //処理のメイン部分(ターンごとの処理)
    void while_game() {
        int loop_cnt = 0;
        while (true) {
            //搬入処理
            table.push_next_container();

            //クレーンを操作(小)
            for (auto &x : smalls) {
                x.update_action(table);
            }

            //クレーンを操作(大)
            big_c.update_action(table);
           
            //搬出処理
            table.pop_container();
            
            loop_cnt++;
            if (loop_cnt == 10000) break;
            //処理の終了条件判定
            if (table.done_all_container()) return;
        }
    }

    void output_answer() {
        cout << big_c.get_actions_string() << endl;
        for (int i = 0; i < n - 1; i++) {
            cout << smalls[i].get_actions_string() << endl;
        }
    }

    private:
    const int n = 5;
    table_class table;
    big_crane big_c;
    vector<small_crane> smalls;
};

int main() {
    int n;
    cin >> n;
    table_class table;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            table.set_next_container(i, x);
        }
    }
    ahc_033 ahc(table);

    ahc.while_game();
    
    ahc.output_answer();
}