Submission #8259447

---

Source Code Expand

// 単純解
#include <bits/stdc++.h>

#include <utility>

#define INF 1e9
using namespace std;

#define REPR(i, n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
void print(const T &value) {
    std::cout << value << std::endl;
}

template<class T>
void errorPrint(const T &value) {
    std::cerr << value << std::endl;
}

typedef long long ll;

string string_from_vector(const std::vector<std::string> &v) {
    string s;
    for (const auto &piece : v) s += piece;
    return s;
}

class Map;

const double LIMIT_TIME_SECOND = 3.0;
enum Direction {
    UP,
    LEFT,
    DOWN,
    RIGHT,
    NONE
};

double time(clock_t st) {
    return (static_cast<double>(clock() - st) / CLOCKS_PER_SEC);
}

template<typename T>
void remove(std::vector<T> &vector, unsigned int index) {
    vector.erase(vector.begin() + index);
}

enum State {
    RANDOM,
    HANDMADE,
    MANHATTAN,
    BLANK
};

class Block {
public:
    pair<int, int> location;

    explicit Block(pair<int, int> loc) {
        location = loc;
    }
};

class Robot {
    int mapSize;
    pair<int, int> location;
    Direction direction = NONE;
    set<pair<int, int>> visited;

    // 一動作
    void move(const Map &);

    // 端処理など
    void goTo(const pair<int, int> &, const Map &);

public:
    bool simulate(const Map &m, pair<int, int> goal) {
        auto bef = location;
        do {
            bef = location;
            move(m);
            if (location == goal) return true;
        } while (bef == location);
        return false;
    }

    explicit Robot(pair<int, int> l, char d, int size) {
        location = l;
        if (d == 'U') direction = UP;
        else if (d == 'D') direction = DOWN;
        else if (d == 'L') direction = LEFT;
        else if (d == 'R') direction = RIGHT;
        else throw logic_error("無効な方向がrobotの初期化に入力されました。");
        mapSize = size;
        visited.insert(location);
    }
};

class DirectionIndicator {
public:
    pair<int, int> location;
    Direction direction;

    explicit DirectionIndicator(pair<int, int> l, char d) {
        if (d == 'U') direction = UP;
        else if (d == 'D') direction = DOWN;
        else if (d == 'L') direction = LEFT;
        else if (d == 'R') direction = RIGHT;
        else throw logic_error("無効な方向がdirection indicatorの初期化に入力されました。");
        location = l;
    }

    explicit DirectionIndicator(pair<int, int> l, Direction d) {
        direction = d;
        location = l;
    }
};

string getStringFromDirection(const Direction &d) {
    switch (d) {
        case UP:
            return "U";
        case DOWN:
            return "D";
        case RIGHT:
            return "R";
        case LEFT:
            return "L";
        case NONE:
            throw logic_error("その方向は存在しません。");
    }
}

class DirectionIndicators {
    DirectionIndicators createManhattanIndicates(int mapSize, pair<int, int> goal);

public:
    set<pair<int, int>> locations;
    vector<DirectionIndicator> directionIndicators;

    explicit DirectionIndicators(const vector<DirectionIndicator> &directionIndis) {
        directionIndicators = directionIndis;
        for (const auto &di:directionIndicators) {
            locations.insert(di.location);
        }
    }

    void update(DirectionIndicator p) {
        locations.insert(p.location);
        REP(i, directionIndicators.size()) {
            if (directionIndicators[i].location == p.location) directionIndicators[i].direction = p.direction;
        }
    }

    explicit DirectionIndicators(int mapSize = 40) {
        random_device rnd;
        int count = rnd() % 1000;
        vector<DirectionIndicator> ds(count, DirectionIndicator(make_pair(0, 0), UP));
        int nowCount = 0;
        while (nowCount != count) {
            int befCount = locations.size();
            pair<int, int> l = make_pair(rnd() % 40, rnd() % 40);
            locations.insert(l);
            // 座標被りの場合は無視して再実行
            if (befCount == locations.size()) continue;
            ds[nowCount] = DirectionIndicator(l, static_cast<Direction>(rnd() % 4));
            nowCount++;
        }
        directionIndicators = ds;
    }

    explicit DirectionIndicators(State s, pair<int, int> goal, int mapSize = 40) {
        DirectionIndicators d;
        switch (s) {
            case RANDOM:
                d = DirectionIndicators(mapSize);
                this->locations = d.locations;
                this->directionIndicators = d.directionIndicators;
                break;
            case MANHATTAN:
                d = createManhattanIndicates(mapSize, goal);
                this->locations = d.locations;
                this->directionIndicators = d.directionIndicators;
                break;
        }
        // マンハッタン距離を使用して方向を一意に定める、
    }

    void print() {
        cout << directionIndicators.size() << endl;
        for (const auto &di: directionIndicators) {
            cout << di.location.first << " " << di.location.second << " " << getStringFromDirection(di.direction)
                 << endl;
        }
    }
};


class Map {
private:
    vector<vector<string>> _backup_map;

    // for backup
    vector<Block> blocks;

    vector<vector<string>> create(int size, const vector<Block> &, const pair<int, int> &goal);

public:
    vector<vector<string>> map;

    void inject(const DirectionIndicators &di) {
        // 一応
        reset();
        for (const auto &d:di.directionIndicators) {
            if (map[d.location.first][d.location.second] == "#") throw logic_error("inject実行前にvalidateしてください");
            else if (map[d.location.first][d.location.second] == "G") throw logic_error("GOALへの案内は不可");
            map[d.location.first][d.location.second] = getStringFromDirection(d.direction);
        }


    }

    DirectionIndicators rand(DirectionIndicators &di, int dd = 3) {
        random_device rnd;
        vector<DirectionIndicator> r;
        pair<int, int> v[8] = {make_pair(-1, -1), make_pair(-1, 0), make_pair(-1, 1), make_pair(0, -1), make_pair(0, 1),
                               make_pair(1, -1), make_pair(1, 0), make_pair(1, 1)};
        for (const auto &d:di.directionIndicators) {
            if (map[d.location.first][d.location.second] == "#") throw logic_error("rand実行前にvalidateしてください");
            else if (map[d.location.first][d.location.second] == "G") throw logic_error("GOALへの案内は不可");
            auto p = make_pair(rnd() % (dd + 1), rnd() % (dd + 1));
            REP(i, 8) {
                auto y = d.location.first + v[i].first;
                auto x = d.location.second + v[i].second;
                if (y >= 40) y -= 40;
                else if (y < 0) y += 40;
                if (x >= 40) x -= 40;
                else if (x < 0) x += 40;
                if (map[y][x] == "#") {
                    REP(k, 8) {
                        if (map[y + v[i].first][x + v[i].second] == "L") {
                            map[y + v[i].first][x + v[i].second] = "R";
                            di.update(DirectionIndicator(make_pair(y + v[i].first, x + v[i].second), 'R'));
                        } else if (map[y + v[i].first][x + v[i].second] == "R") {
                            map[y + v[i].first][x + v[i].second] = "L";
                            di.update(DirectionIndicator(make_pair(y + v[i].first, x + v[i].second), 'L'));
                        } else if (map[y + v[i].first][x + v[i].second] == "U") {
                            map[y + v[i].first][x + v[i].second] = "D";
                            di.update(DirectionIndicator(make_pair(y + v[i].first, x + v[i].second), 'D'));
                        } else if (map[y + v[i].first][x + v[i].second] == "D") {
                            map[y + v[i].first][x + v[i].second] = "U";
                            di.update(DirectionIndicator(make_pair(y + v[i].first, x + v[i].second), 'U'));
                        }
                    }
                }
            }
            map[d.location.first][d.location.second] = getStringFromDirection(d.direction);
        }


    }

    // 案内に#は含まれていないか
    DirectionIndicators validateDirectionIndicator(const DirectionIndicators &di) {
        vector<DirectionIndicator> r;
        for (const auto &d:di.directionIndicators) {
            if (map[d.location.first][d.location.second] == "#") continue;
            r.emplace_back(make_pair(d.location.first, d.location.second), d.direction);
        }
        return DirectionIndicators(r);

    }

    explicit Map(int size, const vector<Block> &bs, const pair<int, int> &goal) {
        map = create(size, bs, goal);
    }

    explicit Map(int size, const vector<Block> &bs, const DirectionIndicators &vdi, const pair<int, int> &goal) {
        map = create(size, bs, goal);
        inject(vdi);
    }

    void reset() {
        map = _backup_map;
    }

    void print() {
        for (const vector<string> &v: this->map) {
            cerr << string_from_vector(v) << endl;
        }
    }
};

// 引数: 行先
void Robot::goTo(const pair<int, int> &p, const Map &m) {
    if (p.first < 0) location.first = mapSize + p.first;
    if (p.second < 0) location.second = mapSize + p.second;
    if (p.first >= mapSize) location.first = p.first - mapSize;
    if (p.second >= mapSize) location.second = p.second - mapSize;
    visited.insert(location);
}

void Robot::move(const Map &m) {
    if (m.map[location.first][location.second] == "U") direction = UP;
    else if (m.map[location.first][location.second] == "D") direction = DOWN;
    else if (m.map[location.first][location.second] == "L") direction = LEFT;
    else if (m.map[location.first][location.second] == "R") direction = RIGHT;
    else if (m.map[location.first][location.second] == "#") throw logic_error("岩の中にいる");
    switch (direction) {
        case UP:
            goTo(make_pair(location.first - 1, location.second), m);
            break;
        case DOWN:
            goTo(make_pair(location.first + 1, location.second), m);
            break;
        case RIGHT:
            goTo(make_pair(location.first, location.second + 1), m);
            break;
        case LEFT:
            goTo(make_pair(location.first, location.second - 1), m);
            break;
        case NONE:
            throw logic_error("ロボットの向きがわかりません");
    }
}

vector<vector<string>> Map::create(int size, const vector<Block> &bs, const pair<int, int> &goal) {
    vector<vector<string>> m(size, vector<string>(size));
    REP(i, size) {
        REP(j, size) m[i][j] = ".";
    }
    for (const auto &block:bs) m[block.location.first][block.location.second] = "#";
    m[goal.first][goal.second] = "G";
    blocks = bs;
    _backup_map = m;
    return m;
}

DirectionIndicators
DirectionIndicators::createManhattanIndicates(int mapSize, pair<int, int> goal) {
    vector<DirectionIndicator> direcI;
    int overY = -1;
    int overX = -1;
    if (goal.first > int(mapSize / 2)) overY = goal.first - int(mapSize / 2);
    else if (goal.first <= int(mapSize / 2)) overY = goal.first + int(mapSize / 2);
    if (goal.second >= int(mapSize / 2)) overX = goal.second - int(mapSize / 2);
    else if (goal.second < int(mapSize / 2)) overX = goal.second + int(mapSize / 2);
    if (overX != -1) {
        if (overX < int(mapSize / 2)) {
            REP(x, overX) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'L');
                direcI.push_back(dd);
            }
            FOR(x, overX, goal.second) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'R');
                direcI.push_back(dd);
            }
            FOR(x, goal.second + 1, mapSize) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'L');
                direcI.push_back(dd);
            }
        } else if (overX >= int(mapSize / 2)) {
            REP(x, goal.second) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'R');
                direcI.push_back(dd);
            }
            FOR(x, goal.second + 1, overX) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'L');
                direcI.push_back(dd);
            }
            FOR(x, overX, mapSize) {
                auto dd = DirectionIndicator(make_pair(goal.first, x), 'R');
                direcI.push_back(dd);
            }
        } else throw logic_error("overXの値がおかしい");
    } else {
        REP(x, int(mapSize/2)) {
            auto dd = DirectionIndicator(make_pair(goal.first, x), 'R');
            direcI.push_back(dd);
        }
        FOR(x, int(mapSize/2)+1, mapSize) {
            auto dd = DirectionIndicator(make_pair(goal.first, x), 'L');
            direcI.push_back(dd);
        }
    }
    if (overY != -1) {
        if (overY < int(mapSize / 2)) {
            REP(y, overY) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'U');
                    direcI.push_back(dd);
                }
            }
            FOR(y, overY, goal.first) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'D');
                    direcI.push_back(dd);
                }
            }
            FOR(y, goal.first + 1, mapSize) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'U');
                    direcI.push_back(dd);
                }
            }
        } else if (overY >= int(mapSize / 2)) {
            REP(y, goal.first) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'D');
                    direcI.push_back(dd);
                }
            }
            FOR(y, goal.first + 1, overY) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'U');
                    direcI.push_back(dd);
                }
            }
            FOR(y, overY, mapSize) {
                REP(x, mapSize) {
                    auto dd = DirectionIndicator(make_pair(y, x), 'D');
                    direcI.push_back(dd);
                }
            }
        } else throw logic_error("overXの値がおかしい");
    }
    return DirectionIndicators(direcI);
}

int main() {
    auto startTime = clock();
    int N, M, B;
    cin >> N >> M >> B;
    int gx, gy;
    cin >> gy >> gx;
    auto goal = make_pair(gy, gx);
    vector<Robot> rbts(M, Robot(make_pair(0, 0), 'U', N));
    REP(i, M) {
        int ry, rx;
        char d;
        cin >> ry >> rx >> d;
        rbts[i] = Robot(make_pair(ry, rx), d, N);
    }
    vector<Block> bks(B, Block(make_pair(0, 0)));
    REP(i, B) {
        int by, bx;
        cin >> by >> bx;
        bks[i] = Block(make_pair(by, bx));
    }
    auto di = DirectionIndicators(MANHATTAN, goal, N);
    auto m = Map(N, bks, goal);
    di = m.validateDirectionIndicator(di);
    di.print();
    cerr << time(startTime) << endl;

    return 0;
}

Submission Info

Judge Result