fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Pos {
  5.     int r, c;
  6.     bool operator==(const Pos &o) const { return r == o.r && c == o.c; }
  7.     bool operator!=(const Pos &o) const { return !(*this == o); }
  8. };
  9.  
  10. struct State {
  11.     Pos player, box;
  12.     int g, h;
  13.     bool operator>(const State &o) const { return g + h > o.g + o.h; }
  14. };
  15.  
  16. struct HashState {
  17.     size_t operator()(const pair<Pos, Pos> &p) const {
  18.         return (p.first.r * 31 + p.first.c) * 131 + (p.second.r * 31 + p.second.c);
  19.     }
  20. };
  21.  
  22. int R = 16, C = 16;
  23. vector<string> grid;
  24. Pos myPos, goalA, goalB;
  25. vector<vector<bool>> isDeadCorner;
  26.  
  27. int dr[4] = {-1, 1, 0, 0};
  28. int dc[4] = {0, 0, -1, 1};
  29. char moveChar[4] = {'U', 'D', 'L', 'R'};
  30.  
  31. bool inBounds(int r, int c) {
  32.     return r >= 0 && r < R && c >= 0 && c < C;
  33. }
  34.  
  35. }bool isWall(int r,int c){ 
  36. 	// be careful !!!!! if we can go into grid with 'b'
  37. 	if (grid[r][c] == 'b') return false;
  38. 	return !inb(r,c) || grid[r][c]=='#'; 
  39. }
  40.  
  41. int manhattan(const Pos &a, const Pos &b) {
  42.     return abs(a.r - b.r) + abs(a.c - b.c);
  43. }
  44.  
  45. // Dead corner precompute
  46. void computeDeadCorners() {
  47.     isDeadCorner.assign(R, vector<bool>(C, false));
  48.     for (int r = 0; r < R; r++) {
  49.         for (int c = 0; c < C; c++) {
  50.             if (grid[r][c] == '#' || Pos{r,c} == goalA) continue;
  51.             bool up = isWall(r - 1, c), down = isWall(r + 1, c);
  52.             bool left = isWall(r, c - 1), right = isWall(r, c + 1);
  53.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  54.                 isDeadCorner[r][c] = true;
  55.             }
  56.         }
  57.     }
  58. }
  59.  
  60. // BFS to see if player can reach targetPos without moving box
  61. bool canReach(Pos start, Pos target, Pos box) {
  62.     queue<Pos> q;
  63.     vector<vector<bool>> vis(R, vector<bool>(C, false));
  64.     q.push(start);
  65.     vis[start.r][start.c] = true;
  66.     while (!q.empty()) {
  67.         Pos cur = q.front(); q.pop();
  68.         if (cur == target) return true;
  69.         for (int k = 0; k < 4; k++) {
  70.             int nr = cur.r + dr[k], nc = cur.c + dc[k];
  71.             if (!inBounds(nr, nc) || vis[nr][nc] || grid[nr][nc] == '#') continue;
  72.             if (nr == box.r && nc == box.c) continue;
  73.             vis[nr][nc] = true;
  74.             q.push({nr, nc});
  75.         }
  76.     }
  77.     return false;
  78. }
  79.  
  80. // A* search: returns path string or ""
  81. string aStarBox(Pos startPlayer, Pos startBox) {
  82.     priority_queue<State, vector<State>, greater<State>> pq;
  83.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  84.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  85.     unordered_set<pair<Pos, Pos>, HashState> visited;
  86.  
  87.     auto heuristic = [&](const Pos &box) {
  88.         return manhattan(box, goalA) * 3;
  89.     };
  90.  
  91.     pq.push({startPlayer, startBox, 0, heuristic(startBox)});
  92.     visited.insert({startPlayer, startBox});
  93.  
  94.     while (!pq.empty()) {
  95.         State cur = pq.top(); pq.pop();
  96.         if (cur.box == goalA) {
  97.             // reconstruct
  98.             string path;
  99.             pair<Pos, Pos> key = {cur.player, cur.box};
  100.             while (parent.count(key)) {
  101.                 path.push_back(moveTaken[key]);
  102.                 key = parent[key];
  103.             }
  104.             reverse(path.begin(), path.end());
  105.             return path;
  106.         }
  107.  
  108.         for (int k = 0; k < 4; k++) {
  109.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  110.             if (!inBounds(newPlayer.r, newPlayer.c) || grid[newPlayer.r][newPlayer.c] == '#') continue;
  111.  
  112.             // push box
  113.             if (newPlayer == cur.box) {
  114.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  115.                 if (isWall(newBox.r, newBox.c) || (isDeadCorner[newBox.r][newBox.c] && newBox != goalA) || newBox == goalB)
  116.                     continue;
  117.                 if (visited.count({newPlayer, newBox})) continue;
  118.                 visited.insert({newPlayer, newBox});
  119.                 pq.push({newPlayer, newBox, cur.g + 1, heuristic(newBox)});
  120.                 parent[{newPlayer, newBox}] = {cur.player, cur.box};
  121.                 moveTaken[{newPlayer, newBox}] = moveChar[k];
  122.             }
  123.             // walk
  124.             else {
  125.                 if (visited.count({newPlayer, cur.box})) continue;
  126.                 visited.insert({newPlayer, cur.box});
  127.                 pq.push({newPlayer, cur.box, cur.g + 1, heuristic(cur.box)});
  128.                 parent[{newPlayer, cur.box}] = {cur.player, cur.box};
  129.                 moveTaken[{newPlayer, cur.box}] = moveChar[k];
  130.             }
  131.         }
  132.     }
  133.     return "";
  134. }
  135.  
  136. int main() {
  137.     ios::sync_with_stdio(false);
  138.     cin.tie(nullptr);
  139.  
  140.     grid.resize(R);
  141.     for (int i = 0; i < R; i++) {
  142.         cin >> grid[i];
  143.         for (int j = 0; j < C; j++) {
  144.             if (grid[i][j] == 'a') myPos = {i, j};
  145.             if (grid[i][j] == 'A') goalA = {i, j};
  146.             if (grid[i][j] == 'B') goalB = {i, j};
  147.         }
  148.     }
  149.  
  150.     computeDeadCorners();
  151.  
  152.     vector<Pos> boxes;
  153.     for (int r = 0; r < R; r++)
  154.         for (int c = 0; c < C; c++)
  155.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  156.  
  157.     string bestPath;
  158.     int bestDist = 1e9;
  159.  
  160.     for (auto &box : boxes) {
  161.         if (isDeadCorner[box.r][box.c] && box != goalA) continue;
  162.         int distToBox = manhattan(myPos, box);
  163.         if (distToBox > 20) continue; // filter far boxes
  164.  
  165.         string path = aStarBox(myPos, box);
  166.         if (!path.empty() && distToBox < bestDist) {
  167.             bestDist = distToBox;
  168.             bestPath = path;
  169.         }
  170.     }
  171.  
  172.     if (!bestPath.empty())
  173.         cout << bestPath[0] << "\n";
  174.     else {
  175.         // random move fallback
  176.         vector<int> dirs = {0, 1, 2, 3};
  177.         random_shuffle(dirs.begin(), dirs.end());
  178.         for (int k : dirs) {
  179.             int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  180.             if (!isWall(nr, nc)) {
  181.                 cout << moveChar[k] << "\n";
  182.                 return 0;
  183.             }
  184.         }
  185.         cout << "U\n"; // default
  186.     }
  187.     return 0;
  188. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
Standard input is empty
stdout 
R
https://ideone.com/jQQOml
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!