fork download
copy 
  1. // enemy_result_priority.cpp
  2. // =========================================
  3. // Bot 'b' ưu tiên kết quả tốt nhất, có xử lý vòng tránh khi gặp 2 hộp liên tiếp
  4. // Đồng thời giữ logic RÀNG BUỘC_B (b không được đi vào vị trí của 'a')
  5. // =========================================
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. struct Pos {
  11.     int r, c;
  12.     bool operator==(const Pos &o) const { return r == o.r && c == o.c; }
  13. };
  14.  
  15. int R = 16, C = 16;
  16. vector<string> grid;
  17. Pos startB, goalB, startA;
  18. vector<Pos> boxes;
  19.  
  20. // 4 hướng di chuyển
  21. int dr[4] = {-1, 1, 0, 0};
  22. int dc[4] = {0, 0, -1, 1};
  23. char dirChar[4] = {'U', 'D', 'L', 'R'};
  24.  
  25. // Kiểm tra ô hợp lệ để đi
  26. bool inBounds(int r, int c) {
  27.     return r >= 0 && r < R && c >= 0 && c < C;
  28. }
  29.  
  30. // Hàm phát hiện góc chết (hộp ở vị trí không thể đẩy về goal)
  31. bool isDeadCorner(const Pos &p) {
  32.     if (p == goalB) return false;
  33.     bool wallUp = (p.r - 1 < 0 || grid[p.r - 1][p.c] == '#');
  34.     bool wallDown = (p.r + 1 >= R || grid[p.r + 1][p.c] == '#');
  35.     bool wallLeft = (p.c - 1 < 0 || grid[p.r][p.c - 1] == '#');
  36.     bool wallRight = (p.c + 1 >= C || grid[p.r][p.c + 1] == '#');
  37.     if ((wallUp && wallLeft) || (wallUp && wallRight) ||
  38.         (wallDown && wallLeft) || (wallDown && wallRight)) {
  39.         return true;
  40.     }
  41.     return false;
  42. }
  43.  
  44. // BFS tìm đường đi từ src đến dest (tránh tường, hộp, và RÀNG BUỘC_B)
  45. vector<char> bfsPath(Pos src, Pos dest) {
  46.     queue<Pos> q;
  47.     map<Pos, Pos> parent;
  48.     map<Pos, char> moveChar;
  49.     set<pair<int,int>> visited;
  50.  
  51.     q.push(src);
  52.     visited.insert({src.r, src.c});
  53.  
  54.     while (!q.empty()) {
  55.         Pos cur = q.front(); q.pop();
  56.         if (cur == dest) {
  57.             vector<char> path;
  58.             Pos p = cur;
  59.             while (!(p == src)) {
  60.                 path.push_back(moveChar[p]);
  61.                 p = parent[p];
  62.             }
  63.             reverse(path.begin(), path.end());
  64.             return path;
  65.         }
  66.         for (int d = 0; d < 4; d++) {
  67.             int nr = cur.r + dr[d];
  68.             int nc = cur.c + dc[d];
  69.             if (!inBounds(nr, nc)) continue;
  70.             if (grid[nr][nc] == '#') continue;
  71.             if (grid[nr][nc] == 'X') continue;
  72.  
  73.             // ===== RÀNG BUỘC_B: 'b' KHÔNG ĐƯỢC ĐI VÀO VỊ TRÍ CỦA 'a' =====
  74.             // Muốn tắt: comment dòng dưới
  75.             if (nr == startA.r && nc == startA.c) continue;
  76.  
  77.             if (!visited.count({nr, nc})) {
  78.                 visited.insert({nr, nc});
  79.                 Pos nxt{nr, nc};
  80.                 parent[nxt] = cur;
  81.                 moveChar[nxt] = dirChar[d];
  82.                 q.push(nxt);
  83.             }
  84.         }
  85.     }
  86.     return {};
  87. }
  88.  
  89. // Tìm vị trí đứng để đẩy hộp về goal
  90. vector<char> findPushPath(const Pos &box) {
  91.     // BFS trạng thái: (vị trí bot, vị trí hộp)
  92.     struct State {
  93.         Pos me, b;
  94.         vector<char> path;
  95.     };
  96.  
  97.     queue<State> q;
  98.     set<tuple<int,int,int,int>> visited;
  99.  
  100.     q.push({startB, box, {}});
  101.     visited.insert({startB.r, startB.c, box.r, box.c});
  102.  
  103.     while (!q.empty()) {
  104.         State cur = q.front(); q.pop();
  105.         if (cur.b == goalB) {
  106.             return cur.path;
  107.         }
  108.         for (int d = 0; d < 4; d++) {
  109.             int mr = cur.me.r + dr[d];
  110.             int mc = cur.me.c + dc[d];
  111.             if (!inBounds(mr, mc) || grid[mr][mc] == '#') continue;
  112.  
  113.             // Nếu di chuyển vào vị trí hộp
  114.             if (mr == cur.b.r && mc == cur.b.c) {
  115.                 int br = cur.b.r + dr[d];
  116.                 int bc = cur.b.c + dc[d];
  117.                 if (!inBounds(br, bc) || grid[br][bc] == '#' || grid[br][bc] == 'X') continue;
  118.                 // Không đẩy vào goal của đối thủ
  119.                 if (grid[br][bc] == 'A') continue;
  120.                 Pos newMe{mr, mc};
  121.                 Pos newBox{br, bc};
  122.                 if (isDeadCorner(newBox)) continue;
  123.                 if (!visited.count({newMe.r, newMe.c, newBox.r, newBox.c})) {
  124.                     visited.insert({newMe.r, newMe.c, newBox.r, newBox.c});
  125.                     auto newPath = cur.path;
  126.                     newPath.push_back(dirChar[d]);
  127.                     q.push({newMe, newBox, newPath});
  128.                 }
  129.             } else {
  130.                 Pos newMe{mr, mc};
  131.                 if (!visited.count({newMe.r, newMe.c, cur.b.r, cur.b.c})) {
  132.                     visited.insert({newMe.r, newMe.c, cur.b.r, cur.b.c});
  133.                     auto newPath = cur.path;
  134.                     newPath.push_back(dirChar[d]);
  135.                     q.push({newMe, cur.b, newPath});
  136.                 }
  137.             }
  138.         }
  139.     }
  140.     return {};
  141. }
  142.  
  143. int main() {
  144.     ios::sync_with_stdio(false);
  145.     cin.tie(nullptr);
  146.  
  147.     grid.resize(R);
  148.     for (int i = 0; i < R; i++) {
  149.         cin >> grid[i];
  150.         for (int j = 0; j < C; j++) {
  151.             if (grid[i][j] == 'b') startB = {i, j};
  152.             if (grid[i][j] == 'B') goalB = {i, j};
  153.             if (grid[i][j] == 'a') startA = {i, j};
  154.             if (grid[i][j] == 'X') boxes.push_back({i, j});
  155.         }
  156.     }
  157.  
  158.     vector<char> bestMove;
  159.     for (auto &box : boxes) {
  160.         if (isDeadCorner(box)) continue;
  161.         auto path = findPushPath(box);
  162.         if (!path.empty()) {
  163.             bestMove = path;
  164.             break;
  165.         }
  166.     }
  167.  
  168.     if (!bestMove.empty()) {
  169.         cout << bestMove[0] << "\n";
  170.     } else {
  171.         cout << "S\n"; // Stay nếu không làm gì
  172.     }
  173.  
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
R
https://ideone.com/XSIFuv
language:
C++14 (gcc 8.3)
created:
4 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!