Editorial for Chairs

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Model every coordinate as a graph node with edges to adjacent coordinates inside the classroom. Each move takes one second. The energy cost of an edge is $1$ ~1~ exactly when one endpoint is a chair and the other is ground; otherwise it is $0$ ~0~.

Run a priority queue ordered by (energy, time). For each coordinate, store the smallest time at which it has been reached so far. When a state is popped, ignore it if a faster arrival at the same coordinate has already been found. Otherwise, expand its four neighbours as long as the current time is below $t$ ~t~.

This works because states are processed in nondecreasing energy order. Any lower-energy way to reach a coordinate is expanded before a higher-energy shortcut can make that coordinate's stored time smaller, so discarding arrivals that are not faster cannot remove a better-energy answer. The first time the TA's coordinate is popped, its energy is therefore minimal among all paths that take at most $t$ ~t~ seconds.

The time complexity is $O(nm \log(nm))$ ~O(nm \log(nm))~.

Solution (C++)

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

using State = tuple<int, int, int, int>;

const array<pair<int, int>, 4> DIRECTIONS {{
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
}};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int a, b, c, d, k, t;
    cin >> a >> b >> c >> d >> k >> t;
    --a;
    --b;
    --c;
    --d;

    vector<vector<int>> grid(n, vector<int>(m));
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        grid[x][y] = 1;
    }

    priority_queue<State, vector<State>, greater<State>> pq;
    vector<vector<int>> min_time(n, vector<int>(m, INT_MAX));

    pq.push({0, 0, a, b});
    min_time[a][b] = 0;

    while (!pq.empty()) {
        auto [energy, time, row, col] = pq.top();
        pq.pop();

        if (time != min_time[row][col]) {
            continue;
        }

        if (row == c && col == d) {
            cout << energy << '\n';
            return 0;
        }

        if (time >= t) {
            continue;
        }

        for (auto [dr, dc] : DIRECTIONS) {
            int nr = row + dr;
            int nc = col + dc;

            if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
                continue;
            }

            int next_energy = energy + (grid[row][col] != grid[nr][nc]);
            int next_time = time + 1;

            if (next_time < min_time[nr][nc]) {
                min_time[nr][nc] = next_time;
                pq.push({next_energy, next_time, nr, nc});
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}

Comments

There are no comments at the moment.