fork(1) 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.     return !inBounds(r, c) || grid[r][c] == '#' || grid[r][c] == 'b';
  37. }
  38.  
  39. int manhattan(const Pos &a, const Pos &b) {
  40.     return abs(a.r - b.r) + abs(a.c - b.c);
  41. }
  42.  
  43. void computeDeadCorners() {
  44.     isDeadCorner.assign(R, vector<bool>(C, false));
  45.     for (int r = 0; r < R; r++) {
  46.         for (int c = 0; c < C; c++) {
  47.             if (grid[r][c] == '#' || Pos{r,c} == goalA) continue;
  48.             bool up = isWall(r - 1, c), down = isWall(r + 1, c);
  49.             bool left = isWall(r, c - 1), right = isWall(r, c + 1);
  50.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  51.                 isDeadCorner[r][c] = true;
  52.             }
  53.         }
  54.     }
  55. }
  56.  
  57. string aStarBox(Pos startPlayer, Pos startBox) {
  58.     priority_queue<State, vector<State>, greater<State>> pq;
  59.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  60.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  61.     unordered_set<pair<Pos, Pos>, HashState> visited;
  62.  
  63.     auto heuristic = [&](const Pos &box) {
  64.         if (box == goalA) return 0; // box đã ở goal → không cần di chuyển
  65.         return manhattan(box, goalA) * 3;
  66.     };
  67.  
  68.     auto nearGoalA = [&](int r, int c) {
  69.         return abs(r - goalA.r) <= 1 && abs(c - goalA.c) <= 1;
  70.     };
  71.  
  72.     pq.push({startPlayer, startBox, 0, heuristic(startBox)});
  73.     visited.insert({startPlayer, startBox});
  74.  
  75.     while (!pq.empty()) {
  76.         State cur = pq.top(); pq.pop();
  77.         if (cur.box == goalA) {
  78.             string path;
  79.             pair<Pos, Pos> key = {cur.player, cur.box};
  80.             while (parent.count(key)) {
  81.                 path.push_back(moveTaken[key]);
  82.                 key = parent[key];
  83.             }
  84.             reverse(path.begin(), path.end());
  85.             return path;
  86.         }
  87.  
  88.         for (int k = 0; k < 4; k++) {
  89.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  90.             if (!inBounds(newPlayer.r, newPlayer.c) || grid[newPlayer.r][newPlayer.c] == '#') continue;
  91.  
  92.             // đẩy box
  93.             if (newPlayer == cur.box) {
  94.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  95.                 if (isWall(newBox.r, newBox.c) || (isDeadCorner[newBox.r][newBox.c] && newBox != goalA) || newBox == goalB)
  96.                     continue;
  97.                 if (visited.count({newPlayer, newBox})) continue;
  98.                 visited.insert({newPlayer, newBox});
  99.                 pq.push({newPlayer, newBox, cur.g + 1, heuristic(newBox)});
  100.                 parent[{newPlayer, newBox}] = {cur.player, cur.box};
  101.                 moveTaken[{newPlayer, newBox}] = moveChar[k];
  102.             }
  103.             // đi bộ
  104.             else {
  105.                 // tránh lang thang gần goalA khi không đẩy box tới đó
  106.                 if (nearGoalA(newPlayer.r, newPlayer.c) && cur.box != goalA) continue;
  107.  
  108.                 if (visited.count({newPlayer, cur.box})) continue;
  109.                 visited.insert({newPlayer, cur.box});
  110.                 pq.push({newPlayer, cur.box, cur.g + 1, heuristic(cur.box)});
  111.                 parent[{newPlayer, cur.box}] = {cur.player, cur.box};
  112.                 moveTaken[{newPlayer, cur.box}] = moveChar[k];
  113.             }
  114.         }
  115.     }
  116.     return "";
  117. }
  118.  
  119. int main() {
  120.     ios::sync_with_stdio(false);
  121.     cin.tie(nullptr);
  122.  
  123.     grid.resize(R);
  124.     for (int i = 0; i < R; i++) {
  125.         cin >> grid[i];
  126.         for (int j = 0; j < C; j++) {
  127.             if (grid[i][j] == 'a') myPos = {i, j};
  128.             if (grid[i][j] == 'A') goalA = {i, j};
  129.             if (grid[i][j] == 'B') goalB = {i, j};
  130.         }
  131.     }
  132.  
  133.     computeDeadCorners();
  134.  
  135.     vector<Pos> boxes;
  136.     for (int r = 0; r < R; r++)
  137.         for (int c = 0; c < C; c++)
  138.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  139.  
  140.     string bestPath;
  141.     int bestDist = 1e9;
  142.  
  143.     for (auto &box : boxes) {
  144.         // bỏ qua hộp đã ở đúng vị trí
  145.         if (box == goalA || box == goalB) continue;
  146.  
  147.         if (isDeadCorner[box.r][box.c] && box != goalA) continue;
  148.         int distToBox = manhattan(myPos, box);
  149.         if (distToBox > 20) continue;
  150.  
  151.         string path = aStarBox(myPos, box);
  152.         if (!path.empty() && distToBox < bestDist) {
  153.             bestDist = distToBox;
  154.             bestPath = path;
  155.         }
  156.     }
  157.  
  158.     if (!bestPath.empty())
  159.         cout << bestPath[0] << "\n";
  160.     else {
  161.         // fallback ngẫu nhiên
  162.         vector<int> dirs = {0, 1, 2, 3};
  163.         random_shuffle(dirs.begin(), dirs.end());
  164.         for (int k : dirs) {
  165.             int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  166.             if (!isWall(nr, nc)) {
  167.                 cout << moveChar[k] << "\n";
  168.                 return 0;
  169.             }
  170.         }
  171.         cout << "U\n"; // default
  172.     }
  173.     return 0;
  174. }
  175.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
R
https://ideone.com/iVt0NG
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!