Novice L/Advanced G: Self Destructing Sokoban Swarm

Formulate a DP.

Dijkstra?

Let's solve this using DP. Let $$$d_{i, j}$$$ be the minimum number of robots required to get one robot on cell $$$(i, j)$$$. At the start, if cell $$$(i, j)$$$ is a spawn point $$$A$$$, then $$$d_{i, j} = 1$$$, otherwise $$$d_{i, j} = \text{INF} = 4 \cdot 10^{18} + 1$$$ to denote that $$$(i, j)$$$ is unreachable.

Let $$$x$$$ be some cell $$$(i, j)$$$ and $$$y$$$ be some cell orthogonally adjacent to $$$x$$$. If $$$d_x, d_y \neq \text{INF}$$$, then the robot in $$$x$$$ can push the robot in $$$y$$$ to cell $$$z$$$ (if cell $$$z$$$ is not an obstacle), setting $$$d_z$$$ to $$$\min(d_z, d_x + d_y)$$$.

Since there is no proper order to process the states, naively looping through the grid $$$nm$$$ times to calculate the states takes $$$\mathcal{O}(n^2m^2)$$$ computations. Although there is no graph nor specific edge weights, Dijkstra's algorithm can be used here. What Dijkstra does is order and process the states in non-decreasing $$$d_{i, j}$$$, eliminating wasted computations. Note that when processing cell $$$x$$$, for some orthogonally adjacent $$$y$$$, both $$$x$$$ pushing $$$y$$$ and $$$y$$$ pushing $$$x$$$ must be considered, for a total of $$$8$$$ transitions per cell. This solves the problem in $$$\mathcal{O}(nm \log nm)$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

const int N = 1005;
const ll inf = (ll)4e18 + 1;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
char grid[N][N];
ll dist[N][N];
int n, m, k, qq;
void solve() {
    cin >> n >> m;
    int tx, ty;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'A') {
                dist[i][j] = 1;
                q.push({1, {i, j}});
            }

            else dist[i][j] = inf;
            if (grid[i][j] == 'B') tx = i, ty = j;
        }
    }

    auto ok = [&](int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#');
    };

    while (!q.empty()) {
        auto [d, p] = q.top();
        auto [x, y] = p;
        q.pop();
        if (d != dist[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            ll nd = d + dist[nx][ny];
            nx += dx[i], ny += dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }

            nx = x - dx[i], ny = y - dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }
        }
    }

    cout << (dist[tx][ty] == inf ? -1 : dist[tx][ty]) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}