# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1125427 | ALTAKEXE | Robots (APIO13_robots) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // Infinity
const int MAX_N = 9; // Maximum number of robots
const int MAX_V = 500 * 500; // Maximum number of reachable grids
int w, h, n; // Width, height, and number of robots
vector<string> grid;
vector<pair<int, int>> robot_positions;
vector<int> reachable_cells; // List of reachable grid IDs
unordered_map<int, int> cell_to_index; // Map grid ID to compressed index
vector<vector<int>> dist; // Distances between reachable cells
// Convert 2D coordinates to a single grid ID
inline int get_id(int x, int y) {
return x * w + y;
}
// Precompute reachable cells and distances
void preprocess() {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue<pair<int, int>> q;
vector<vector<bool>> visited(h, vector<bool>(w, false));
// Start BFS from all robot positions
for (auto [x, y] : robot_positions) {
q.push({x, y});