oj.uz

Submission #998528

# Submission time Handle Problem Language Result Execution time Memory
998528 2024-06-14T07:32:40 Z Ibrohim0704 Robots (APIO13_robots) C++17
10 / 100
 1 ms 440 KB 
#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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -