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.         // simple custom hash
  19.         return (p.first.r * 31 + p.first.c) * 131 + (p.second.r * 31 + p.second.c);
  20.     }
  21. };
  22.  
  23. int R = 16, C = 16;
  24. vector<string> grid;
  25. Pos myPos, goalA, goalB;
  26. vector<vector<bool>> isDeadCorner;
  27.  
  28. // Directions
  29. int dr[4] = {-1, 1, 0, 0};
  30. int dc[4] = {0, 0, -1, 1};
  31. char moveChar[4] = {'U', 'D', 'L', 'R'};
  32.  
  33. bool inBounds(int r, int c) {
  34.     return r >= 0 && r < R && c >= 0 && c < C;
  35. }
  36.  
  37. // Hard wall: chỉ tường thật sự '#' hoặc ngoài biên
  38. bool isHardWall(int r, int c) {
  39.     return !inBounds(r, c) || grid[r][c] == '#';
  40. }
  41.  
  42. // Walk-block: dùng cho bước đi bình thường (bao gồm 'b' là chặn)
  43. bool isWalkBlocked(int r, int c) {
  44.     return !inBounds(r, c) || grid[r][c] == '#' || grid[r][c] == 'b';
  45. }
  46.  
  47. int manhattan(const Pos &a, const Pos &b) {
  48.     return abs(a.r - b.r) + abs(a.c - b.c);
  49. }
  50.  
  51. // Dead corner precompute: nếu 1 ô trống kề 2 bức tường theo góc vuông (không tính goalA)
  52. void computeDeadCorners() {
  53.     isDeadCorner.assign(R, vector<bool>(C, false));
  54.     for (int r = 0; r < R; r++) {
  55.         for (int c = 0; c < C; c++) {
  56.             if (!inBounds(r,c)) continue;
  57.             if (grid[r][c] == '#') continue;
  58.             if (Pos{r,c} == goalA) continue;
  59.             bool up = isHardWall(r - 1, c), down = isHardWall(r + 1, c);
  60.             bool left = isHardWall(r, c - 1), right = isHardWall(r, c + 1);
  61.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  62.                 isDeadCorner[r][c] = true;
  63.             }
  64.         }
  65.     }
  66. }
  67.  
  68. /*
  69. ####
  70. .X..
  71. .aX.
  72. ....
  73. */
  74.  
  75. // A* search: returns path string (sequence of 'U','D','L','R') or "" if impossible
  76. string aStarBox(Pos startPlayer, Pos startBox) {
  77.     priority_queue<State, vector<State>, greater<State>> pq;
  78.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  79.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  80.     unordered_map<pair<Pos, Pos>, int, HashState> bestDistToGoal;
  81.  
  82.     auto heuristic = [&](const Pos &box) {
  83.         return manhattan(box, goalA) * 3;
  84.     };
  85.  
  86.     auto boxDist = [&](const Pos &b) {
  87.         return manhattan(b, goalA);
  88.     };
  89.  
  90.     pq.push({startPlayer, startBox, 0, heuristic(startBox)});
  91.     bestDistToGoal[{startPlayer, startBox}] = boxDist(startBox);
  92.  
  93.     while (!pq.empty()) {
  94.         State cur = pq.top(); pq.pop();
  95.  
  96.         // goal: box on goalA
  97.         if (cur.box == goalA) {
  98.             // reconstruct path
  99.             string path;
  100.             pair<Pos, Pos> key = {cur.player, cur.box};
  101.             while (parent.count(key)) {
  102.                 path.push_back(moveTaken[key]);
  103.                 key = parent[key];
  104.             }
  105.             reverse(path.begin(), path.end());
  106.             return path;
  107.         }
  108.  
  109.         for (int k = 0; k < 4; k++) {
  110.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  111.  
  112.             // --- walk case (bình thường) ---
  113.             if (!(newPlayer == cur.box)) {
  114.                 // If walk blocked (includes 'b'), skip
  115.                 if (isWalkBlocked(newPlayer.r, newPlayer.c)) continue;
  116.  
  117.                 pair<Pos,Pos> nxtKey = {newPlayer, cur.box};
  118.                 int ndist = boxDist(cur.box);
  119.                 if (!bestDistToGoal.count(nxtKey) || ndist < bestDistToGoal[nxtKey]) {
  120.                     bestDistToGoal[nxtKey] = ndist;
  121.                     parent[nxtKey] = {cur.player, cur.box};
  122.                     moveTaken[nxtKey] = moveChar[k];
  123.                     pq.push({newPlayer, cur.box, cur.g + 1, heuristic(cur.box)});
  124.                 }
  125.             }
  126.             // --- push case ---
  127.             else {
  128.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  129.  
  130.                 // 1) newBox must be in bounds and not a hard wall ('#')
  131.                 if (!inBounds(newBox.r, newBox.c)) continue;
  132.                 if (isHardWall(newBox.r, newBox.c)) continue;
  133.  
  134.                 // 2) disallow pushing into 'b' (other actor) — treat as blocked for push
  135.                 if (grid[newBox.r][newBox.c] == 'b') continue;
  136.  
  137.                 // 3) disallow pushing into another box (unless that cell is goalA and you allow stacking)
  138.                 if (grid[newBox.r][newBox.c] == 'X' && !(newBox == goalA)) continue;
  139.  
  140.                 // 4) disallow pushing into dead corner (unless it's goalA)
  141.                 if (isDeadCorner[newBox.r][newBox.c] && !(newBox == goalA)) continue;
  142.  
  143.                 // 5) disallow pushing into opponent goal B
  144.                 if (newBox == goalB) continue;
  145.  
  146.                 // pass checks -> consider new state
  147.                 pair<Pos,Pos> nxtKey = {newPlayer, newBox};
  148.                 int ndist = boxDist(newBox);
  149.                 if (!bestDistToGoal.count(nxtKey) || ndist < bestDistToGoal[nxtKey]) {
  150.                     bestDistToGoal[nxtKey] = ndist;
  151.                     parent[nxtKey] = {cur.player, cur.box};
  152.                     moveTaken[nxtKey] = moveChar[k];
  153.                     pq.push({newPlayer, newBox, cur.g + 1, heuristic(newBox)});
  154.                 }
  155.             }
  156.         }
  157.     }
  158.  
  159.     return "";
  160. }
  161.  
  162. int main() {
  163.     ios::sync_with_stdio(false);
  164.     cin.tie(nullptr);
  165.  
  166.     // Read grid (R x C assumed 16x16 by default)
  167.     grid.resize(R);
  168.     for (int i = 0; i < R; i++) {
  169.         cin >> grid[i];
  170.         for (int j = 0; j < C; j++) {
  171.             if (grid[i][j] == 'a') myPos = {i, j};
  172.             if (grid[i][j] == 'A') goalA = {i, j};
  173.             if (grid[i][j] == 'B') goalB = {i, j};
  174.         }
  175.     }
  176.  
  177.     computeDeadCorners();
  178.  
  179.     // Gather boxes
  180.     vector<Pos> boxes;
  181.     for (int r = 0; r < R; r++)
  182.         for (int c = 0; c < C; c++)
  183.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  184.  
  185.     // Greedy: choose nearest box (by manhattan to player) that A* can plan for
  186.     string bestPath;
  187.     int bestDist = INT_MAX;
  188.     for (auto &box : boxes) {
  189.         // skip if box already in dead corner (and not goal)
  190.         if (isDeadCorner[box.r][box.c] && box != goalA) continue;
  191.         int distToBox = manhattan(myPos, box);
  192.         if (distToBox > 50) continue; // optional prune for very far boxes
  193.         string path = aStarBox(myPos, box);
  194.         if (!path.empty() && distToBox < bestDist) {
  195.             bestDist = distToBox;
  196.             bestPath = path;
  197.         }
  198.     }
  199.  
  200.     if (!bestPath.empty()) {
  201.         cout << bestPath[0] << "\n";
  202.         return 0;
  203.     }
  204.  
  205.     // fallback: random legal move (respecting isWalkBlocked)
  206.     vector<int> dirs = {0,1,2,3};
  207.     random_shuffle(dirs.begin(), dirs.end());
  208.     for (int k : dirs) {
  209.         int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  210.         if (!inBounds(nr,nc)) continue;
  211.         if (isWalkBlocked(nr,nc)) continue;
  212.         if (grid[nr][nc] == 'X') continue; // don't step onto other box
  213.         cout << moveChar[k] << "\n";
  214.         return 0;
  215.     }
  216.  
  217.     cout << "S\n";
  218.     return 0;
  219. }
  220.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
R
https://ideone.com/r0KXmE
language:
C++14 (gcc 8.3)
created:
3 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!