Submission #49982930

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

Num n {0};
constexpr Num MaxLen = 64;
constexpr Num N_Cells = MaxLen * MaxLen;
constexpr Num N_States = N_Cells * N_Cells;
bool grid[MaxLen][MaxLen];

Num position_to_state(Num y, Num x) {
    return y * MaxLen + x;
}

std::pair<Num, Num> to_yxs(Num state) {
    const Num y = state / MaxLen;
    const Num x = state % MaxLen;
    return std::make_pair(y, x);
}

Num board_state(Num y1, Num x1, Num y2, Num x2) {
    const Num s1 = position_to_state(y1, x1);
    const Num s2 = position_to_state(y2, x2);
    return (s1 == s2) ? 0 : (s1 * N_Cells + s2);
}

std::tuple<Num, Num, Num, Num> to_positions(Num state) {
    const auto [y1, x1] = to_yxs(state / N_Cells);
    const auto [y2, x2] = to_yxs(state % N_Cells);
    return std::make_tuple(y1, x1, y2, x2);
}

void solve(std::istream& is, std::ostream& os) {
    is >> n;

    for(Num y{0}; y<=(n+1); ++y) {
        for(Num x{0}; x<=(n+1); ++x) {
            grid[y][x] = true;
        }
    }

    std::vector<std::pair<Num, Num>> ps;
    for(Num y{1}; y<=n; ++y) {
        std::string s;
        is >> s;

        for(Num x{1}; x<=n; ++x) {
            const auto c = s.at(x-1);
            grid[y][x] = (c == '#');
            if (c == 'P') {
                ps.push_back(std::make_pair(y, x));
            }
        }
    }

    const std::vector<std::pair<Num, Num>> dyxs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    using Distance = int64_t;
    constexpr Num Inf = std::numeric_limits<Distance>::max() / 2;
    std::vector<Distance> distances(N_States, Inf);

    Q<std::pair<Num, Num>> q;
    const auto start = board_state(ps.at(0).first, ps.at(0).second, ps.at(1).first, ps.at(1).second);
    q.push(std::make_pair(0, start));
    while(!q.empty()) {
        const auto [dist, from] = q.front();
        q.pop();

        if (distances.at(from) <= dist) {
            continue;
        }
        distances.at(from) = dist;

        const auto next_dist = dist + 1;
        for(const auto& [dy, dx] : dyxs) {
            const auto [y1, x1, y2, x2] = to_positions(from);
                if (grid[y1][x1] || grid[y2][x2]) {
                    continue;
                }

                Num ny1 = y1 + dy;
                Num nx1 = x1 + dx;
                if (grid[ny1][nx1]) {
                    ny1 = y1;
                    nx1 = x1;
                }

                Num ny2 = y2 + dy;
                Num nx2 = x2 + dx;
                if (grid[ny2][nx2]) {
                    ny2 = y2;
                    nx2 = x2;
                }

                const auto to = board_state(ny1, nx1, ny2, nx2);
                if (from == to) {
                    continue;
                }

                if (distances.at(to) <= next_dist) {
                    continue;
                }
                q.push(std::make_pair(next_dist, to));
            }
    }

    auto answer = distances.at(0);
    if (answer >= Inf) {
        answer = -1;
    }

    os << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result