Submission #995601

#TimeUsernameProblemLanguageResultExecution timeMemory
995601Ibrohim0704Robots (APIO13_robots)C++14
0 / 100
315 ms163840 KiB
#include <iostream> #include <queue> #include <vector> #include <map> using namespace std; // Define grid dimensions const int MAX_WIDTH = 500; const int MAX_HEIGHT = 500; // Define movement directions const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; // Function to check if a position is valid (within grid boundaries and not obstructed) bool isValid(int x, int y, int width, int height, const vector<string>& grid) { return x >= 0 && x < width && y >= 0 && y < height && grid[y][x] != 'x'; } // Function to simulate robot movement and merging pair<int, int> moveRobot(int x, int y, int dir, const vector<string>& grid) { int nx = x, ny = y; while (isValid(nx + dx[dir], ny + dy[dir], grid[0].size(), grid.size(), grid)) { nx += dx[dir]; ny += dy[dir]; if (isdigit(grid[ny][nx])) { return make_pair(nx, ny); } } return make_pair(x, y); } // BFS function to find minimum pushes int minPushes(int n, int width, int height, const vector<string>& grid) { map<int, bool> mergedWith; map<int, pair<int, int>> robotPositions; map<pair<int, int>, char> rotatingPlates; // Find initial positions of robots and rotating plates for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { if (isdigit(grid[y][x])) { int robotNum = grid[y][x] - '0'; robotPositions[robotNum] = make_pair(x, y); } else if (grid[y][x] == 'A' || grid[y][x] == 'C') { rotatingPlates[make_pair(x, y)] = grid[y][x]; } } } // Initialize BFS queue with initial robot positions queue<pair<map<int, pair<int, int>>, int>> q; q.push(make_pair(robotPositions, 0)); // Perform BFS while (!q.empty()) { auto current = q.front(); q.pop(); auto currentPositions = current.first; int pushes = current.second; bool allMerged = true; for (int i = 1; i <= n; i++) { if (!mergedWith[i]) { allMerged = false; break; } } if (allMerged) { return pushes; } for (auto& robot : currentPositions) { int robotNum = robot.first; int x = robot.second.first; int y = robot.second.second; if (mergedWith[robotNum]) { continue; } for (int d = 0; d < 4; d++) { int nx, ny; tie(nx, ny) = moveRobot(x, y, d, grid); if (make_pair(nx, ny) != make_pair(x, y)) { map<int, pair<int, int>> newPositions = currentPositions; newPositions[robotNum] = make_pair(nx, ny); q.push(make_pair(newPositions, pushes + 1)); } } } } return -1; // Merging not possible } int main() { int n, width, height; cin >> n >> width >> height; vector<string> grid(height); for (int i = 0; i < height; i++) { cin >> grid[i]; } int result = minPushes(n, width, height, grid); cout << result << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...