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.     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. // A* search: returns path string or ""
  58. string aStarBox(Pos startPlayer, Pos startBox) {
  59.     priority_queue<State, vector<State>, greater<State>> pq;
  60.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  61.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  62.  
  63.     // Lưu khoảng cách tốt nhất từng gặp từ box đến A
  64.     unordered_map<pair<Pos, Pos>, int, HashState> bestDistToGoal;
  65.  
  66.     auto heuristic = [&](const Pos &box) {
  67.         return manhattan(box, goalA) * 3;
  68.     };
  69.  
  70.     auto boxDist = [&](const Pos &b) {
  71.         return manhattan(b, goalA);
  72.     };
  73.  
  74.     pq.push({startPlayer, startBox, 0, heuristic(startBox)});
  75.     bestDistToGoal[{startPlayer, startBox}] = boxDist(startBox);
  76.  
  77.     while (!pq.empty()) {
  78.         State cur = pq.top(); pq.pop();
  79.         if (cur.box == goalA) {
  80.             // reconstruct
  81.             string path;
  82.             pair<Pos, Pos> key = {cur.player, cur.box};
  83.             while (parent.count(key)) {
  84.                 path.push_back(moveTaken[key]);
  85.                 key = parent[key];
  86.             }
  87.             reverse(path.begin(), path.end());
  88.             return path;
  89.         }
  90.  
  91.         for (int k = 0; k < 4; k++) {
  92.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  93.             if (isWall(newPlayer.r, newPlayer.c)) continue;
  94.  
  95.             // push box
  96.             if (newPlayer == cur.box) {
  97.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  98.                 if (isWall(newBox.r, newBox.c) || (isDeadCorner[newBox.r][newBox.c] && newBox != goalA) || newBox == goalB)
  99.                     continue;
  100.  
  101.                 int ndist = boxDist(newBox);
  102.                 auto key = make_pair(newPlayer, newBox);
  103.  
  104.                 // Chỉ cho vào nếu chưa thấy hoặc thấy nhưng hộp tiến gần hơn
  105.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key]) {
  106.                     bestDistToGoal[key] = ndist;
  107.                     pq.push({newPlayer, newBox, cur.g + 1, heuristic(newBox)});
  108.                     parent[key] = {cur.player, cur.box};
  109.                     moveTaken[key] = moveChar[k];
  110.                 }
  111.             }
  112.             // walk
  113.             else {
  114.                 auto key = make_pair(newPlayer, cur.box);
  115.                 int ndist = boxDist(cur.box);
  116.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key]) {
  117.                     bestDistToGoal[key] = ndist;
  118.                     pq.push({newPlayer, cur.box, cur.g + 1, heuristic(cur.box)});
  119.                     parent[key] = {cur.player, cur.box};
  120.                     moveTaken[key] = moveChar[k];
  121.                 }
  122.             }
  123.         }
  124.     }
  125.     return "";
  126. }
  127.  
  128. int main() {
  129.     ios::sync_with_stdio(false);
  130.     cin.tie(nullptr);
  131.  
  132.     grid.resize(R);
  133.     for (int i = 0; i < R; i++) {
  134.         cin >> grid[i];
  135.         for (int j = 0; j < C; j++) {
  136.             if (grid[i][j] == 'a') myPos = {i, j};
  137.             if (grid[i][j] == 'A') goalA = {i, j};
  138.             if (grid[i][j] == 'B') goalB = {i, j};
  139.         }
  140.     }
  141.  
  142.     computeDeadCorners();
  143.  
  144.     vector<Pos> boxes;
  145.     for (int r = 0; r < R; r++)
  146.         for (int c = 0; c < C; c++)
  147.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  148.  
  149.     string bestPath;
  150.     int bestDist = 1e9;
  151.  
  152.     for (auto &box : boxes) {
  153.         if (isDeadCorner[box.r][box.c] && box != goalA) continue;
  154.         int distToBox = manhattan(myPos, box);
  155.         if (distToBox > 20) continue; // filter far boxes
  156.  
  157.         string path = aStarBox(myPos, box);
  158.         if (!path.empty() && distToBox < bestDist) {
  159.             bestDist = distToBox;
  160.             bestPath = path;
  161.         }
  162.     }
  163.  
  164.     if (!bestPath.empty())
  165.         cout << bestPath[0] << "\n";
  166.     else {
  167.         // random move fallback
  168.         vector<int> dirs = {0, 1, 2, 3};
  169.         random_shuffle(dirs.begin(), dirs.end());
  170.         for (int k : dirs) {
  171.             int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  172.             if (!isWall(nr, nc)) {
  173.                 cout << moveChar[k] << "\n";
  174.                 return 0;
  175.             }
  176.         }
  177.         cout << "U\n"; // default
  178.     }
  179.     return 0;
  180. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
R
https://ideone.com/pnbd0P
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!