A22558 动物园 全站第一个题解

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <algorithm>

int n_val;
int p_val;
int r_val;
std::vector<std::string> grid;
std::vector<std::pair<int, int>> cage_locations;
std::vector<int> animal_speeds;
std::vector<std::vector<std::vector<int>>> dists;
std::vector<std::vector<int>> possible_cages_for_animal;
std::vector<int> final_assignment;
std::vector<bool> is_cage_used;

void run_bfs_from_cage(int cage_idx_0_based) {
    auto [start_r, start_c] = cage_locations[cage_idx_0_based];
    dists[cage_idx_0_based].assign(n_val + 1, std::vector<int>(n_val + 1, -1));

    if (grid[start_r - 1][start_c - 1] == '*') {
        return;
    }

    std::queue<std::pair<int, int>> q;
    q.push({start_r, start_c});
    dists[cage_idx_0_based][start_r][start_c] = 0;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int next_r = r + dr[i];
            int next_c = c + dc[i];

            if (next_r >= 1 && next_r <= n_val && next_c >= 1 && next_c <= n_val &&
                grid[next_r - 1][next_c - 1] == '.' && dists[cage_idx_0_based][next_r][next_c] == -1) {
                dists[cage_idx_0_based][next_r][next_c] = dists[cage_idx_0_based][r][c] + 1;
                q.push({next_r, next_c});
            }
        }
    }
}

void build_distance_maps() {
    dists.resize(p_val);
    for (int i = 0; i < p_val; ++i) {
        run_bfs_from_cage(i);
    }
}

void determine_possible_cages(const std::vector<std::vector<std::tuple<int, int, int>>>& sightings_by_animal) {
    possible_cages_for_animal.resize(p_val + 1);
    for (int j = 1; j <= p_val; ++j) {
        for (int k = 1; k <= p_val; ++k) {
            bool is_k_possible = true;
            int speed = animal_speeds[j - 1];
            
            for (const auto& sighting : sightings_by_animal[j]) {
                auto [t, x, y] = sighting;
                int dist = dists[k - 1][x][y];
                if (dist == -1 || (long long)dist > (long long)speed * t) {
                    is_k_possible = false;
                    break;
                }
            }
            if (is_k_possible) {
                possible_cages_for_animal[j].push_back(k);
            }
        }
    }
}

bool find_assignment(int animal_k) {
    if (animal_k > p_val) {
        return true;
    }

    for (int cage_idx_1_based : possible_cages_for_animal[animal_k]) {
        if (!is_cage_used[cage_idx_1_based]) {
            is_cage_used[cage_idx_1_based] = true;
            final_assignment[animal_k] = cage_idx_1_based;
            if (find_assignment(animal_k + 1)) {
                return true;
            }
            is_cage_used[cage_idx_1_based] = false;
        }
    }
    return false;
}

void solve() {
    std::cin >> n_val;
    grid.resize(n_val);
    for (int i = 0; i < n_val; ++i) {
        std::cin >> grid[i];
    }
    
    std::cin >> p_val;
    cage_locations.resize(p_val);
    for (int i = 0; i < p_val; ++i) {
        std::cin >> cage_locations[i].first >> cage_locations[i].second;
    }
    
    animal_speeds.resize(p_val);
    for (int i = 0; i < p_val; ++i) {
        std::cin >> animal_speeds[i];
    }

    std::cin >> r_val;
    std::vector<std::vector<std::tuple<int, int, int>>> sightings_by_animal(p_val + 1);
    for (int i = 0; i < r_val; ++i) {
        int t, x, y, j;
        std::cin >> t >> x >> y >> j;
        sightings_by_animal[j].emplace_back(t, x, y);
    }

    build_distance_maps();
    
    determine_possible_cages(sightings_by_animal);
    
    final_assignment.resize(p_val + 1);
    is_cage_used.resize(p_val + 1, false);

    if (find_assignment(1)) {
        for (int i = 1; i <= p_val; ++i) {
            int animal_id = i;
            int cage_id = final_assignment[i];
            auto [r, c] = cage_locations[cage_id - 1];
            std::cout << animal_id << " " << r << " " << c << '\n';
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}