fork download
copy 
  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;
  25. vector<Pos> goalsA, goalsB;
  26. vector<vector<bool>> isDeadCorner;
  27.  
  28. int dr[4] = {-1, 1, 0, 0};
  29. int dc[4] = {0, 0, -1, 1};
  30. char moveChar[4] = {'U', 'D', 'L', 'R'};
  31.  
  32. bool avoidB = true; // switch: true = tránh ô 'b', false = cho phép đi vào 'b'
  33.  
  34. bool inBounds(int r, int c) {
  35.     return r >= 0 && r < R && c >= 0 && c < C;
  36. }
  37.  
  38. bool isWall(int r, int c) {
  39.     if (!inBounds(r, c)) return true;
  40.     if (grid[r][c] == '#') return true;
  41.     if (avoidB && grid[r][c] == 'b') return true;
  42.     return false;
  43. }
  44.  
  45. int manhattan(const Pos &a, const Pos &b) {
  46.     return abs(a.r - b.r) + abs(a.c - b.c);
  47. }
  48.  
  49. bool isGoalA(const Pos &p) {
  50.     for (auto &g : goalsA) if (p == g) return true;
  51.     return false;
  52. }
  53.  
  54. bool isGoalB(const Pos &p) {
  55.     for (auto &g : goalsB) if (p == g) return true;
  56.     return false;
  57. }
  58.  
  59. int minDistGoalA(const Pos &b) {
  60.     int d = 1e9;
  61.     for (auto &g : goalsA) d = min(d, manhattan(b, g));
  62.     return d;
  63. }
  64.  
  65. void computeDeadCorners() {
  66.     isDeadCorner.assign(R, vector<bool>(C, false));
  67.     for (int r = 0; r < R; r++) {
  68.         for (int c = 0; c < C; c++) {
  69.             if (grid[r][c] == '#' || isGoalA({r, c})) continue;
  70.             bool up = isWall(r - 1, c), down = isWall(r + 1, c);
  71.             bool left = isWall(r, c - 1), right = isWall(r, c + 1);
  72.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  73.                 isDeadCorner[r][c] = true;
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. // A* search (keeps anti-loop, limit on g, heuristic combining box->goal and player->box)
  80. string aStarBox(Pos startPlayer, Pos startBox) {
  81.     priority_queue<State, vector<State>, greater<State>> pq;
  82.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  83.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  84.     unordered_map<pair<Pos, Pos>, int, HashState> bestDistToGoal;
  85.  
  86.     auto heuristic = [&](const Pos &player, const Pos &box) {
  87.         return minDistGoalA(box) * 3 + manhattan(player, box);
  88.     };
  89.  
  90.     auto boxDist = [&](const Pos &b) {
  91.         return minDistGoalA(b);
  92.     };
  93.  
  94.     pq.push({startPlayer, startBox, 0, heuristic(startPlayer, startBox)});
  95.     bestDistToGoal[{startPlayer, startBox}] = boxDist(startBox);
  96.  
  97.     while (!pq.empty()) {
  98.         State cur = pq.top(); pq.pop();
  99.  
  100.         // if box already on any goalA
  101.         if (isGoalA(cur.box)) {
  102.             string path;
  103.             pair<Pos, Pos> key = {cur.player, cur.box};
  104.             while (parent.count(key)) {
  105.                 path.push_back(moveTaken[key]);
  106.                 key = parent[key];
  107.             }
  108.             reverse(path.begin(), path.end());
  109.             return path;
  110.         }
  111.  
  112.         // Limit search depth to avoid huge expansions
  113.         if (cur.g > 60) continue;
  114.  
  115.         for (int k = 0; k < 4; k++) {
  116.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  117.             if (isWall(newPlayer.r, newPlayer.c)) continue;
  118.  
  119.             // push case
  120.             if (newPlayer == cur.box) {
  121.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  122.                 if (isWall(newBox.r, newBox.c) || (isDeadCorner[newBox.r][newBox.c] && !isGoalA(newBox)) || isGoalB(newBox))
  123.                     continue;
  124.  
  125.                 int ndist = boxDist(newBox);
  126.                 auto key = make_pair(newPlayer, newBox);
  127.                 bool leavingGoal = isGoalA(cur.player) || isGoalA(newPlayer);
  128.  
  129.                 // anti-loop: allow push if new state unseen, or box closer,
  130.                 // or if leaving a goal cell (so player can move away)
  131.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key] ||
  132.                     (leavingGoal && ndist > 0 && ndist <= bestDistToGoal[key])) {
  133.                     bestDistToGoal[key] = ndist;
  134.                     pq.push({newPlayer, newBox, cur.g + 1, heuristic(newPlayer, newBox)});
  135.                     parent[key] = {cur.player, cur.box};
  136.                     moveTaken[key] = moveChar[k];
  137.                 }
  138.             }
  139.             // walk case
  140.             else {
  141.                 auto key = make_pair(newPlayer, cur.box);
  142.                 int ndist = boxDist(cur.box);
  143.                 bool leavingGoal = isGoalA(cur.player) || isGoalA(newPlayer);
  144.  
  145.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key] ||
  146.                     (leavingGoal && ndist > 0 && ndist <= bestDistToGoal[key])) {
  147.                     bestDistToGoal[key] = ndist;
  148.                     pq.push({newPlayer, cur.box, cur.g + 1, heuristic(newPlayer, cur.box)});
  149.                     parent[key] = {cur.player, cur.box};
  150.                     moveTaken[key] = moveChar[k];
  151.                 }
  152.             }
  153.         }
  154.     }
  155.  
  156.     return "";
  157. }
  158.  
  159. int main() {
  160.     ios::sync_with_stdio(false);
  161.     cin.tie(nullptr);
  162.  
  163.     grid.resize(R);
  164.     for (int i = 0; i < R; i++) {
  165.         cin >> grid[i];
  166.         for (int j = 0; j < C; j++) {
  167.             if (grid[i][j] == 'a') myPos = {i, j};
  168.             if (grid[i][j] == 'A') goalsA.push_back({i, j});
  169.             if (grid[i][j] == 'B') goalsB.push_back({i, j});
  170.         }
  171.     }
  172.  
  173.     computeDeadCorners();
  174.  
  175.     // gather boxes
  176.     vector<Pos> boxes;
  177.     for (int r = 0; r < R; r++)
  178.         for (int c = 0; c < C; c++)
  179.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  180.  
  181.     // Sort boxes by distance to player (nearest first)
  182.     sort(boxes.begin(), boxes.end(), [&](const Pos &p1, const Pos &p2) {
  183.         return manhattan(myPos, p1) < manhattan(myPos, p2);
  184.     });
  185.  
  186.     string chosenPath;
  187.     // Try A* on nearest boxes in order; stop at first success
  188.     for (auto &box : boxes) {
  189.         if (isDeadCorner[box.r][box.c] && !isGoalA(box)) continue;
  190.         int distToBox = manhattan(myPos, box);
  191.         if (distToBox > 20) continue; // optional far filter
  192.         string path = aStarBox(myPos, box);
  193.         if (!path.empty()) {
  194.             chosenPath = path;
  195.             break; // stop after finding path to nearest feasible box
  196.         }
  197.     }
  198.  
  199.     if (!chosenPath.empty()) {
  200.         cout << chosenPath[0] << "\n";
  201.         return 0;
  202.     }
  203.  
  204.     // fallback: random legal move
  205.     vector<int> dirs = {0, 1, 2, 3};
  206.     random_shuffle(dirs.begin(), dirs.end());
  207.     for (int k : dirs) {
  208.         int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  209.         if (!isWall(nr, nc)) {
  210.             cout << moveChar[k] << "\n";
  211.             return 0;
  212.         }
  213.     }
  214.  
  215.     cout << "U\n";
  216.     return 0;
  217. }
  218.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
R
https://ideone.com/UhM2jo
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!