This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;
struct State {
map<int, pair<int, int>> positions;
int pushes;
};
bool is_within_bounds(int x, int y, int w, int h) {
return 0 <= x && x < w && 0 <= y && y < h;
}
pair<int, int> move_robot(int y, int x, int dy, int dx, const vector<vector<char>>& grid, int w, int h) {
while (is_within_bounds(x + dx, y + dy, w, h) && grid[y + dy][x + dx] != 'x') {
y += dy;
x += dx;
if (grid[y][x] == 'A') {
swap(dy, dx);
dx = -dx;
} else if (grid[y][x] == 'C') {
swap(dy, dx);
dy = -dy;
}
}
return {y, x};
}
int bfs(int n, int w, int h, const vector<vector<char>>& grid, const map<int, pair<int, int>>& initial_positions) {
queue<State> q;
set<map<int, pair<int, int>>> visited;
q.push({initial_positions, 0});
visited.insert(initial_positions);
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
while (!q.empty()) {
State current_state = q.front();
q.pop();
if (current_state.positions.size() == 1 && current_state.positions.begin()->first == 1) {
return current_state.pushes;
}
for (const auto& robot : current_state.positions) {
int label = robot.first;
int y = robot.second.first;
int x = robot.second.second;
for (const auto& dir : directions) {
int dy = dir.first;
int dx = dir.second;
auto [new_y, new_x] = move_robot(y, x, dy, dx, grid, w, h);
map<int, pair<int, int>> new_positions = current_state.positions;
new_positions[label] = {new_y, new_x};
map<pair<int, int>, vector<int>> merged_positions;
for (const auto& pos : new_positions) {
merged_positions[{pos.second.first, pos.second.second}].push_back(pos.first);
}
map<int, pair<int, int>> next_positions;
for (const auto& pos : merged_positions) {
int min_label = *min_element(pos.second.begin(), pos.second.end());
int max_label = *max_element(pos.second.begin(), pos.second.end());
next_positions[min_label] = pos.first;
if (min_label != max_label) {
next_positions.erase(max_label);
}
}
if (visited.find(next_positions) == visited.end()) {
visited.insert(next_positions);
q.push({next_positions, current_state.pushes + 1});
}
}
}
}
return -1;
}
int main() {
int n, w, h;
cin >> n >> w >> h;
vector<vector<char>> grid(h, vector<char>(w));
map<int, pair<int, int>> initial_positions;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> grid[i][j];
if (isdigit(grid[i][j])) {
initial_positions[grid[i][j] - '0'] = {i, j};
}
}
}
int result = bfs(n, w, h, grid, initial_positions);
cout << result << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |