#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <set>
using namespace std;
const int MAX_W = 10;
const int MAX_H = 10;
const int INF = 10000; // Large enough number to simulate "infinity"
char grid[MAX_H][MAX_W];
int w, h;
bool is_inside(int x, int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}
vector<pair<int, int>> get_moves(int x, int y) {
vector<pair<int, int>> positions;
// Directions: Up, Down, Left, Right
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
for (int d = 0; d < 4; ++d) {
int nx = x, ny = y;
while (is_inside(nx + dx[d], ny + dy[d]) && grid[nx + dx[d]][ny + dy[d]] != 'x') {
nx += dx[d];
ny += dy[d];
}
positions.push_back({nx, ny});
}
return positions;
}
int simulate(vector<int> &moves, pair<int, int> robot1, pair<int, int> robot2) {
int move_count = 0;
for (int move : moves) {
pair<int, int> new_position;
if (move < 4) { // Moves for robot1
new_position = get_moves(robot1.first, robot1.second)[move];
robot1 = new_position;
} else { // Moves for robot2
new_position = get_moves(robot2.first, robot2.second)[move - 4];
robot2 = new_position;
}
move_count++;
if (robot1 == robot2) {
return move_count;
}
}
return INF;
}
int brute_force(pair<int, int> robot1, pair<int, int> robot2) {
int best = INF;
vector<int> current_moves;
int depth_limit = 10; // Reasonable depth limit based on grid constraints
// A recursive function to explore all possible move sequences up to depth_limit
function<void(int)> explore = [&](int depth) {
if (depth == depth_limit) {
int result = simulate(current_moves, robot1, robot2);
best = min(best, result);
return;
}
for (int i = 0; i < 8; i++) { // 4 directions for each robot
current_moves.push_back(i);
explore(depth + 1);
current_moves.pop_back();
}
};
explore(0);
return best == INF ? -1 : best;
}
int main() {
cin >> w >> h;
pair<int, int> robot1, robot2;
bool first_robot_found = false;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> grid[i][j];
if (isdigit(grid[i][j])) {
if (!first_robot_found) {
robot1 = {i, j};
first_robot_found = true;
} else {
robot2 = {i, j};
}
}
}
}
cout << brute_force(robot1, robot2) << endl;
return 0;
}
Compilation message
robots.cpp: In function 'int brute_force(std::pair<int, int>, std::pair<int, int>)':
robots.cpp:61:5: error: 'function' was not declared in this scope
61 | function<void(int)> explore = [&](int depth) {
| ^~~~~~~~
robots.cpp:6:1: note: 'std::function' is defined in header '<functional>'; did you forget to '#include <functional>'?
5 | #include <set>
+++ |+#include <functional>
6 | using namespace std;
robots.cpp:61:14: error: expected primary-expression before 'void'
61 | function<void(int)> explore = [&](int depth) {
| ^~~~
robots.cpp:75:5: error: 'explore' was not declared in this scope
75 | explore(0);
| ^~~~~~~
robots.cpp:58:9: warning: unused variable 'depth_limit' [-Wunused-variable]
58 | int depth_limit = 10; // Reasonable depth limit based on grid constraints
| ^~~~~~~~~~~
