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. };
  8.  
  9. struct State {
  10.     Pos player, box;
  11.     int g, h;
  12.     bool operator>(const State &o) const { return g + h > o.g + o.h; }
  13. };
  14.  
  15. // key lưu trạng thái player + box
  16. struct StateKey {
  17.     Pos p, b;
  18.     bool operator==(const StateKey &o) const {
  19.         return p.r == o.p.r && p.c == o.p.c && b.r == o.b.r && b.c == o.b.c;
  20.     }
  21. };
  22.  
  23. struct StateKeyHash {
  24.     size_t operator()(const StateKey &k) const {
  25.         return ((k.p.r * 31 + k.p.c) << 16) ^ (k.b.r * 31 + k.b.c);
  26.     }
  27. };
  28.  
  29. int R = 16, C = 16;
  30. vector<string> grid;
  31. Pos myPos;
  32. vector<Pos> goalsA, goalsB;
  33. vector<vector<bool>> isDeadCorner;
  34. vector<vector<int>> distGoalA;
  35.  
  36. int dr[4] = {-1, 1, 0, 0};
  37. int dc[4] = {0, 0, -1, 1};
  38. char moveChar[4] = {'U', 'D', 'L', 'R'};
  39.  
  40. bool avoidB = true;
  41.  
  42. bool inBounds(int r, int c) {
  43.     return r >= 0 && r < R && c >= 0 && c < C;
  44. }
  45.  
  46. bool isWall(int r, int c) {
  47.     if (!inBounds(r, c)) return true;
  48.     if (grid[r][c] == '#') return true;
  49.     if (avoidB && grid[r][c] == 'b') return true;
  50.     return false;
  51. }
  52.  
  53. bool isGoalA(const Pos &p) {
  54.     for (auto &g : goalsA) if (p == g) return true;
  55.     return false;
  56. }
  57.  
  58. bool isGoalB(const Pos &p) {
  59.     for (auto &g : goalsB) if (p == g) return true;
  60.     return false;
  61. }
  62.  
  63. void computeDeadCorners() {
  64.     isDeadCorner.assign(R, vector<bool>(C, false));
  65.     for (int r = 0; r < R; r++) {
  66.         for (int c = 0; c < C; c++) {
  67.             if (grid[r][c] == '#' || isGoalA({r, c})) continue;
  68.             bool up = isWall(r - 1, c), down = isWall(r + 1, c);
  69.             bool left = isWall(r, c - 1), right = isWall(r, c + 1);
  70.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  71.                 isDeadCorner[r][c] = true;
  72.             }
  73.         }
  74.     }
  75. }
  76.  
  77. void precomputeDistGoalA() {
  78.     distGoalA.assign(R, vector<int>(C, 1e9));
  79.     for (int r = 0; r < R; r++) {
  80.         for (int c = 0; c < C; c++) {
  81.             for (auto &g : goalsA) {
  82.                 distGoalA[r][c] = min(distGoalA[r][c], abs(r - g.r) + abs(c - g.c));
  83.             }
  84.         }
  85.     }
  86. }
  87.  
  88. string aStarBox(Pos startPlayer, Pos startBox) {
  89.     priority_queue<State, vector<State>, greater<State>> pq;
  90.     unordered_map<StateKey, StateKey, StateKeyHash> parent;
  91.     unordered_map<StateKey, char, StateKeyHash> moveTaken;
  92.     unordered_map<StateKey, int, StateKeyHash> bestDistToGoal;
  93.  
  94.     auto heuristic = [&](const Pos &player, const Pos &box) {
  95.         return distGoalA[box.r][box.c] * 3 + abs(player.r - box.r) + abs(player.c - box.c);
  96.     };
  97.  
  98.     auto boxDist = [&](const Pos &b) {
  99.         return distGoalA[b.r][b.c];
  100.     };
  101.  
  102.     pq.push({startPlayer, startBox, 0, heuristic(startPlayer, startBox)});
  103.     bestDistToGoal[{startPlayer, startBox}] = boxDist(startBox);
  104.  
  105.     while (!pq.empty()) {
  106.         State cur = pq.top(); pq.pop();
  107.  
  108.         if (isGoalA(cur.box)) {
  109.             string path;
  110.             StateKey key = {cur.player, cur.box};
  111.             while (parent.count(key)) {
  112.                 path.push_back(moveTaken[key]);
  113.                 key = parent[key];
  114.             }
  115.             reverse(path.begin(), path.end());
  116.             return path;
  117.         }
  118.  
  119.         if (cur.g > 40) continue; // giới hạn độ sâu
  120.  
  121.         for (int k = 0; k < 4; k++) {
  122.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  123.             if (isWall(newPlayer.r, newPlayer.c)) continue;
  124.  
  125.             if (newPlayer == cur.box) { // push
  126.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  127.                 if (isWall(newBox.r, newBox.c) || (isDeadCorner[newBox.r][newBox.c] && !isGoalA(newBox)) || isGoalB(newBox))
  128.                     continue;
  129.  
  130.                 int ndist = boxDist(newBox);
  131.                 StateKey key = {newPlayer, newBox};
  132.                 bool leavingGoal = isGoalA(cur.player) || isGoalA(newPlayer);
  133.  
  134.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key] ||
  135.                     (leavingGoal && ndist > 0 && ndist <= bestDistToGoal[key])) {
  136.                     bestDistToGoal[key] = ndist;
  137.                     pq.push({newPlayer, newBox, cur.g + 1, heuristic(newPlayer, newBox)});
  138.                     parent[key] = {cur.player, cur.box};
  139.                     moveTaken[key] = moveChar[k];
  140.                 }
  141.             } 
  142.             else { // walk
  143.                 StateKey key = {newPlayer, cur.box};
  144.                 int ndist = boxDist(cur.box);
  145.                 bool leavingGoal = isGoalA(cur.player) || isGoalA(newPlayer);
  146.  
  147.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key] ||
  148.                     (leavingGoal && ndist > 0 && ndist <= bestDistToGoal[key])) {
  149.                     bestDistToGoal[key] = ndist;
  150.                     pq.push({newPlayer, cur.box, cur.g + 1, heuristic(newPlayer, cur.box)});
  151.                     parent[key] = {cur.player, cur.box};
  152.                     moveTaken[key] = moveChar[k];
  153.                 }
  154.             }
  155.         }
  156.     }
  157.     return "";
  158. }
  159.  
  160. int main() {
  161.     ios::sync_with_stdio(false);
  162.     cin.tie(nullptr);
  163.  
  164.     grid.resize(R);
  165.     for (int i = 0; i < R; i++) {
  166.         cin >> grid[i];
  167.         for (int j = 0; j < C; j++) {
  168.             if (grid[i][j] == 'a') myPos = {i, j};
  169.             if (grid[i][j] == 'A') goalsA.push_back({i, j});
  170.             if (grid[i][j] == 'B') goalsB.push_back({i, j});
  171.         }
  172.     }
  173.  
  174.     computeDeadCorners();
  175.     precomputeDistGoalA();
  176.  
  177.     vector<Pos> boxes;
  178.     for (int r = 0; r < R; r++)
  179.         for (int c = 0; c < C; c++)
  180.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  181.  
  182.     // Ưu tiên box gần nhất (player→box + box→goal)
  183.     sort(boxes.begin(), boxes.end(), [&](const Pos &p1, const Pos &p2) {
  184.         int d1 = abs(myPos.r - p1.r) + abs(myPos.c - p1.c) + distGoalA[p1.r][p1.c];
  185.         int d2 = abs(myPos.r - p2.r) + abs(myPos.c - p2.c) + distGoalA[p2.r][p2.c];
  186.         return d1 < d2;
  187.     });
  188.  
  189.     string chosenPath;
  190.     for (auto &box : boxes) {
  191.         if (isDeadCorner[box.r][box.c] && !isGoalA(box)) continue;
  192.         if (abs(myPos.r - box.r) + abs(myPos.c - box.c) > 20) continue;
  193.         string path = aStarBox(myPos, box);
  194.         if (!path.empty()) {
  195.             chosenPath = path;
  196.             break;
  197.         }
  198.     }
  199.  
  200.     if (!chosenPath.empty()) {
  201.         cout << chosenPath[0] << "\n";
  202.         return 0;
  203.     }
  204.  
  205.     // fallback
  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 (!isWall(nr, nc)) {
  211.             cout << moveChar[k] << "\n";
  212.             return 0;
  213.         }
  214.     }
  215.  
  216.     cout << "U\n";
  217.     return 0;
  218. }
  219.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
R
https://ideone.com/BoRatV
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!