fork download
copy 
  1. // sokoban_push_with_feasibility_fix_aXX_final.cpp
  2. // C++14
  3. // Giữ nguyên logic gốc, thêm: nhiều goal A + bỏ qua hộp kề mà ngay sau nó có 'X' (không phải A)
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. struct Pos {
  9.     int r, c;
  10.     bool operator==(const Pos &o) const { return r == o.r && c == o.c; }
  11.     bool operator!=(const Pos &o) const { return !(*this == o); }
  12. };
  13.  
  14. // For using pair<Pos,Pos> in unordered containers
  15. struct HashState {
  16.     size_t operator()(const pair<Pos, Pos> &p) const {
  17.         return (p.first.r * 31 + p.first.c) * 131 + (p.second.r * 31 + p.second.c);
  18.     }
  19. };
  20.  
  21. int R = 16, C = 16;
  22. vector<string> grid;
  23. Pos myPos;
  24. vector<Pos> goalsA;
  25. Pos goalB = {-1,-1};
  26. vector<vector<bool>> isDeadCorner;
  27.  
  28. // Directions: Up, Down, Left, Right
  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: only real wall '#' or outside bounds
  38. bool isHardWall(int r, int c) {
  39.     return !inBounds(r, c) || grid[r][c] == '#';
  40. }
  41.  
  42. // Walk-block: used for normal walking (treat 'b' as block for walking)
  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. bool isGoalA(const Pos &p) {
  52.     for (size_t i = 0; i < goalsA.size(); ++i) if (goalsA[i] == p) return true;
  53.     return false;
  54. }
  55.  
  56. Pos nearestGoalA(const Pos &b) {
  57.     if (goalsA.empty()) return Pos{-1,-1};
  58.     Pos best = goalsA[0];
  59.     int bd = manhattan(b, best);
  60.     for (size_t i = 1; i < goalsA.size(); ++i) {
  61.         int d = manhattan(b, goalsA[i]);
  62.         if (d < bd) { bd = d; best = goalsA[i]; }
  63.     }
  64.     return best;
  65. }
  66.  
  67. // Dead corner precompute: nếu 1 ô trống kề 2 bức tường theo góc vuông (không tính goalA)
  68. void computeDeadCorners() {
  69.     isDeadCorner.assign(R, vector<bool>(C, false));
  70.     for (int r = 0; r < R; r++) {
  71.         for (int c = 0; c < C; c++) {
  72.             if (!inBounds(r,c)) continue;
  73.             if (grid[r][c] == '#') continue;
  74.             if (isGoalA(Pos{r,c})) continue;
  75.             bool up = isHardWall(r - 1, c), down = isHardWall(r + 1, c);
  76.             bool left = isHardWall(r, c - 1), right = isHardWall(r, c + 1);
  77.             if ((up && left) || (up && right) || (down && left) || (down && right)) {
  78.                 isDeadCorner[r][c] = true;
  79.             }
  80.         }
  81.     }
  82. }
  83.  
  84. // ------------------ helper canReach ------------------
  85. // BFS to see if player can reach targetPos without moving box
  86. // Respects isWalkBlocked() and treats the specified box cell as blocked.
  87. bool canReach(const Pos &start, const Pos &target, const Pos &box) {
  88.     if (!inBounds(start.r, start.c) || !inBounds(target.r, target.c)) return false;
  89.     vector<vector<char>> vis(R, vector<char>(C, 0));
  90.     queue<Pos> q;
  91.     vis[start.r][start.c] = 1;
  92.     q.push(start);
  93.     while (!q.empty()) {
  94.         Pos cur = q.front(); q.pop();
  95.         if (cur == target) return true;
  96.         for (int d = 0; d < 4; ++d) {
  97.             int nr = cur.r + dr[d], nc = cur.c + dc[d];
  98.             if (!inBounds(nr,nc)) continue;
  99.             if (vis[nr][nc]) continue;
  100.             if (isWalkBlocked(nr,nc)) continue;
  101.             // cannot step onto the box cell
  102.             if (nr == box.r && nc == box.c) continue;
  103.             vis[nr][nc] = 1;
  104.             q.push({nr,nc});
  105.         }
  106.     }
  107.     return false;
  108. }
  109.  
  110. // ------------------ boxCanReachGoal ------------------
  111. // BFS on push-states (boxPos, playerPos) to see whether the box can be pushed to any goalA
  112. // Rules used:
  113. //   - Player moves must avoid walls and cannot step into box cell.
  114. //   - A push from box -> ahead is valid if ahead is not a hard wall, not another box (unless that cell is goalA), not goalB, not dead-corner (unless goalA).
  115. bool boxCanReachGoal(const Pos &boxStart, const Pos &playerStart) {
  116.     if (isGoalA(boxStart)) return true;
  117.  
  118.     unordered_set<pair<Pos, Pos>, HashState> vis;
  119.     queue<pair<Pos,Pos>> q;
  120.     vis.insert({boxStart, playerStart});
  121.     q.push({boxStart, playerStart});
  122.  
  123.     while (!q.empty()) {
  124.         pair<Pos,Pos> st = q.front(); q.pop();
  125.         Pos b = st.first;
  126.         Pos p = st.second;
  127.  
  128.         for (int d = 0; d < 4; ++d) {
  129.             int behind_r = b.r - dr[d], behind_c = b.c - dc[d]; // where player must stand
  130.             int ahead_r = b.r + dr[d], ahead_c = b.c + dc[d];  // box will move here
  131.  
  132.             // check ahead
  133.             if (!inBounds(ahead_r, ahead_c)) continue;
  134.             if (isHardWall(ahead_r, ahead_c)) continue;
  135.             if (grid[ahead_r][ahead_c] == 'X' && !isGoalA(Pos{ahead_r,ahead_c})) continue;
  136.             if (Pos{ahead_r,ahead_c} == goalB) continue;
  137.             if (isDeadCorner[ahead_r][ahead_c] && !isGoalA(Pos{ahead_r,ahead_c})) continue;
  138.  
  139.             // behind must be valid
  140.             if (!inBounds(behind_r, behind_c)) continue;
  141.             if (isWalkBlocked(behind_r, behind_c)) continue;
  142.             if (grid[behind_r][behind_c] == 'X' && !(behind_r==b.r && behind_c==b.c)) continue;
  143.  
  144.             // player must reach behind without moving b
  145.             if (!canReach(p, Pos{behind_r, behind_c}, b)) continue;
  146.  
  147.             Pos newBox = Pos{ahead_r, ahead_c};
  148.             Pos newPlayer = b;
  149.             if (isGoalA(newBox)) return true;
  150.  
  151.             pair<Pos,Pos> newState = {newBox, newPlayer};
  152.             if (!vis.count(newState)) {
  153.                 vis.insert(newState);
  154.                 q.push(newState);
  155.             }
  156.         }
  157.     }
  158.  
  159.     return false;
  160. }
  161.  
  162. // -------------------- A* (find path to nearest goalA for this box) --------------------
  163. struct State2 {
  164.     Pos player, box;
  165.     int g, h;
  166.     bool operator>(const State2 &o) const { return g + h > o.g + o.h; }
  167. };
  168.  
  169. // A*: tìm đường đưa box startBox đến targetGoal (nearestGoalA(startBox))
  170. // Tránh sửa logic gốc về các ràng buộc push/walk
  171. string aStarBox(Pos startPlayer, Pos startBox) {
  172.     Pos targetGoal = nearestGoalA(startBox);
  173.     if (targetGoal.r == -1) return "";
  174.  
  175.     priority_queue<State2, vector<State2>, greater<State2>> pq;
  176.     unordered_map<pair<Pos, Pos>, pair<Pos, Pos>, HashState> parent;
  177.     unordered_map<pair<Pos, Pos>, char, HashState> moveTaken;
  178.     unordered_map<pair<Pos, Pos>, int, HashState> bestDistToGoal;
  179.  
  180.     auto boxDist = [&](const Pos &b)->int {
  181.         return manhattan(b, targetGoal);
  182.     };
  183.  
  184.     auto heuristic = [&](const Pos &player, const Pos &box)->int {
  185.         return boxDist(box) * 3 + manhattan(player, box);
  186.     };
  187.  
  188.     pq.push({startPlayer, startBox, 0, heuristic(startPlayer, startBox)});
  189.     bestDistToGoal[{startPlayer, startBox}] = boxDist(startBox);
  190.  
  191.     while (!pq.empty()) {
  192.         State2 cur = pq.top(); pq.pop();
  193.  
  194.         // goal: box on any goalA
  195.         if (isGoalA(cur.box)) {
  196.             string path;
  197.             pair<Pos, Pos> key = {cur.player, cur.box};
  198.             while (parent.count(key)) {
  199.                 path.push_back(moveTaken[key]);
  200.                 key = parent[key];
  201.             }
  202.             reverse(path.begin(), path.end());
  203.             return path;
  204.         }
  205.  
  206.         // safety depth limit
  207.         if (cur.g > 200) continue;
  208.  
  209.         for (int k = 0; k < 4; ++k) {
  210.             Pos newPlayer = {cur.player.r + dr[k], cur.player.c + dc[k]};
  211.  
  212.             // WALK case
  213.             if (!(newPlayer == cur.box)) {
  214.                 if (isWalkBlocked(newPlayer.r, newPlayer.c)) continue;
  215.                 pair<Pos,Pos> key = {newPlayer, cur.box};
  216.                 int ndist = boxDist(cur.box);
  217.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key]) {
  218.                     bestDistToGoal[key] = ndist;
  219.                     parent[key] = {cur.player, cur.box};
  220.                     moveTaken[key] = moveChar[k];
  221.                     pq.push({newPlayer, cur.box, cur.g + 1, heuristic(newPlayer, cur.box)});
  222.                 }
  223.             }
  224.             // PUSH case
  225.             else {
  226.                 Pos newBox = {cur.box.r + dr[k], cur.box.c + dc[k]};
  227.  
  228.                 // 1) newBox must be in bounds and not a hard wall ('#')
  229.                 if (!inBounds(newBox.r, newBox.c)) continue;
  230.                 if (isHardWall(newBox.r, newBox.c)) continue;
  231.  
  232.                 // 2) disallow pushing into 'b'
  233.                 if (grid[newBox.r][newBox.c] == 'b') continue;
  234.  
  235.                 // 3) disallow pushing into another box (unless that cell is goalA)
  236.                 if (grid[newBox.r][newBox.c] == 'X' && !isGoalA(newBox)) continue;
  237.  
  238.                 // 4) disallow pushing into dead corner (unless it's goalA)
  239.                 if (isDeadCorner[newBox.r][newBox.c] && !isGoalA(newBox)) continue;
  240.  
  241.                 // 5) disallow pushing into opponent goal B
  242.                 if (newBox == goalB) continue;
  243.  
  244.                 pair<Pos,Pos> key = {newPlayer, newBox};
  245.                 int ndist = boxDist(newBox);
  246.                 if (!bestDistToGoal.count(key) || ndist < bestDistToGoal[key]) {
  247.                     bestDistToGoal[key] = ndist;
  248.                     parent[key] = {cur.player, cur.box};
  249.                     moveTaken[key] = moveChar[k];
  250.                     pq.push({newPlayer, newBox, cur.g + 1, heuristic(newPlayer, newBox)});
  251.                 }
  252.             }
  253.         }
  254.     }
  255.  
  256.     return "";
  257. }
  258.  
  259. // -------------------- main (selection uses feasibility + aXX guard) --------------------
  260. int main() {
  261.     ios::sync_with_stdio(false);
  262.     cin.tie(nullptr);
  263.  
  264.     // Read grid (R x C assumed 16x16 by default)
  265.     grid.resize(R);
  266.     for (int i = 0; i < R; i++) {
  267.         cin >> grid[i];
  268.         for (int j = 0; j < C; j++) {
  269.             if (grid[i][j] == 'a') myPos = {i, j};
  270.             if (grid[i][j] == 'A') goalsA.push_back({i, j});
  271.             if (grid[i][j] == 'B') goalB = {i, j};
  272.         }
  273.     }
  274.  
  275.     computeDeadCorners();
  276.  
  277.     // Gather boxes
  278.     vector<Pos> boxes;
  279.     for (int r = 0; r < R; r++)
  280.         for (int c = 0; c < C; c++)
  281.             if (grid[r][c] == 'X') boxes.push_back({r, c});
  282.  
  283.     // If no boxes -> stay
  284.     if (boxes.empty()) {
  285.         cout << "S\n";
  286.         return 0;
  287.     }
  288.  
  289.     string bestPath;
  290.     int bestDist = INT_MAX;
  291.  
  292.     // Scan boxes (prefer nearer ones)
  293.     for (size_t i = 0; i < boxes.size(); ++i) {
  294.         Pos box = boxes[i];
  295.  
  296.         // skip dead corner boxes (unless the box is on some A)
  297.         if (isDeadCorner[box.r][box.c] && !isGoalA(box)) continue;
  298.  
  299.         int distToBox = manhattan(myPos, box);
  300.         if (distToBox > 50) continue; // optional prune for very far boxes
  301.  
  302.         // --- FIX for aXX:
  303.         // If player is adjacent to this box (dist == 1) and the cell beyond the box in that direction
  304.         // is an 'X' that is NOT a goalA, then immediate push from player would hit another box -> skip this box.
  305.         if (distToBox == 1) {
  306.             int dirR = box.r - myPos.r;
  307.             int dirC = box.c - myPos.c;
  308.             int dir = -1;
  309.             for (int k = 0; k < 4; ++k) {
  310.                 if (dr[k] == dirR && dc[k] == dirC) { dir = k; break; }
  311.             }
  312.             if (dir != -1) {
  313.                 int beyond_r = box.r + dr[dir], beyond_c = box.c + dc[dir];
  314.                 if (inBounds(beyond_r, beyond_c) && grid[beyond_r][beyond_c] == 'X' && !isGoalA(Pos{beyond_r,beyond_c})) {
  315.                     // skip this box — it's the aXX pattern (player adjacent but pushing that way hits another X)
  316.                     continue;
  317.                 }
  318.             }
  319.         }
  320.  
  321.         // Feasibility check — only consider this box if it can be pushed to some goal A
  322.         if (!boxCanReachGoal(box, myPos)) continue;
  323.  
  324.         string path = aStarBox(myPos, box);
  325.         if (!path.empty() && distToBox < bestDist) {
  326.             bestDist = distToBox;
  327.             bestPath = path;
  328.         }
  329.     }
  330.  
  331.     if (!bestPath.empty()) {
  332.         cout << bestPath[0] << "\n";
  333.         return 0;
  334.     }
  335.  
  336.     // fallback: random legal move (respecting isWalkBlocked)
  337.     vector<int> dirs = {0,1,2,3};
  338.     random_shuffle(dirs.begin(), dirs.end());
  339.     for (int k : dirs) {
  340.         int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  341.         if (!inBounds(nr,nc)) continue;
  342.         if (isWalkBlocked(nr,nc)) continue;
  343.         if (grid[nr][nc] == 'X') continue; // don't step onto other box
  344.         cout << moveChar[k] << "\n";
  345.         return 0;
  346.     }
  347.  
  348.     cout << "S\n";
  349.     return 0;
  350. }
  351.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
R
https://ideone.com/DqM7Q4
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!