fork download 
  1. // me_optimal.cpp
  2. // Compile: g++ -std=c++14 me_optimal.cpp -O2 -o me_optimal.exe
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. struct Pos { int r,c; };
  7. inline bool operator==(Pos a, Pos b){ return a.r==b.r && a.c==b.c; }
  8. inline bool operator!=(Pos a, Pos b){ return !(a==b); }
  9.  
  10. int R=16, C=16;
  11. vector<string> grid;
  12. Pos myPos, oppPos, goalA, goalB;
  13. vector<vector<bool>> isDeadCorner;
  14. vector<Pos> boxes;
  15.  
  16. int dr[4]={-1,1,0,0}, dc[4]={0,0,-1,1};
  17. char mvChar[4]={'U','D','L','R'};
  18.  
  19. bool inb(int r,int c){ return r>=0 && r<R && c>=0 && c<C; }
  20. bool isWall(int r,int c){ 
  21. 	// be careful !!!!! if we can go into grid with 'b'
  22. 	// if (grid[r][c] == 'b') return false;
  23. 	return !inb(r,c) || grid[r][c]=='#'; 
  24. }
  25. int manhattan(const Pos &a, const Pos &b){ return abs(a.r-b.r)+abs(a.c-b.c); }
  26.  
  27. void computeDeadCorners(){
  28.     isDeadCorner.assign(R, vector<bool>(C,false));
  29.     for(int r=0;r<R;r++){
  30.         for(int c=0;c<C;c++){
  31.             if(grid[r][c]=='#') continue;
  32.             if(Pos{r,c}==goalA || Pos{r,c}==goalB) continue;
  33.             bool up = isWall(r-1,c);
  34.             bool down = isWall(r+1,c);
  35.             bool left = isWall(r,c-1);
  36.             bool right = isWall(r,c+1);
  37.             if((up && left) || (up && right) || (down && left) || (down && right))
  38.                 isDeadCorner[r][c] = true;
  39.         }
  40.     }
  41. }
  42.  
  43. // Pack state (pr,pc,br,bc,pushedFlag) into uint32_t key
  44. inline uint32_t packKey(int pr,int pc,int br,int bc,int pushed){
  45.     // fields: 6 bits each (0..63) plenty for 16
  46.     return (uint32_t)pr | ((uint32_t)pc<<6) | ((uint32_t)br<<12) | ((uint32_t)bc<<18) | ((uint32_t)pushed<<24);
  47. }
  48. void unpackKey(uint32_t k,int &pr,int &pc,int &br,int &bc,int &pushed){
  49.     pr = k & 63;
  50.     pc = (k>>6) & 63;
  51.     br = (k>>12) & 63;
  52.     bc = (k>>18) & 63;
  53.     pushed = (k>>24) & 1;
  54. }
  55.  
  56. struct Node {
  57.     int pr,pc,br,bc;
  58.     int g,h;
  59.     bool operator<(Node const& o) const {
  60.         return g+h > o.g+o.h; // min-heap via priority_queue
  61.     }
  62. };
  63.  
  64. string aStar_withPushed(const Pos &startP, const Pos &startB, const vector<vector<char>> &boxMap){
  65.     // A* over (player, box, pushedLast)
  66.     priority_queue<Node> pq;
  67.     unordered_map<uint32_t, uint32_t> parent; // child -> parent key
  68.     unordered_map<uint32_t, char> moveTaken;  // child -> move char
  69.     unordered_set<uint32_t> visited;
  70.  
  71.     auto heuristic = [&](int br,int bc,int pr,int pc){
  72.         // stronger heuristic: box->goal * 3 + player->box
  73.         return manhattan(Pos{br,bc}, goalA) * 3 + manhattan(Pos{pr,pc}, Pos{br,bc});
  74.     };
  75.  
  76.     int initH = heuristic(startB.r,startB.c,startP.r,startP.c);
  77.     pq.push({startP.r, startP.c, startB.r, startB.c, 0, initH});
  78.     uint32_t initKey = packKey(startP.r,startP.c,startB.r,startB.c,0);
  79.     visited.insert(initKey);
  80.     parent[initKey] = initKey; // root
  81.  
  82.     while(!pq.empty()){
  83.         Node cur = pq.top(); pq.pop();
  84.         uint32_t curKey = packKey(cur.pr,cur.pc,cur.br,cur.bc,0); // pushed flag not stored in node struct; we must reconstruct pushed flag by parent map?
  85.         // Actually we need explicit pushed flag per node; adjust: store pushed in key and Node not store it. Let's redo.
  86.  
  87.         // break (we won't reach here, placeholder)
  88.         break;
  89.     }
  90.  
  91.     // Because above pattern needs pushed flag, implement proper loop with explicit pushed flag in key
  92.     // Re-implement using open-set priority queue of tuples
  93.     struct PQItem { int pr,pc,br,bc; int g,h; int pushed; };
  94.     struct PQCmp { bool operator()(PQItem const& a, PQItem const& b) const { return a.g + a.h > b.g + b.h; } };
  95.     priority_queue<PQItem, vector<PQItem>, PQCmp> open;
  96.     open.push({startP.r,startP.c,startB.r,startB.c,0,heuristic(startB.r,startB.c,startP.r,startP.c),0});
  97.     uint32_t startKey = packKey(startP.r,startP.c,startB.r,startB.c,0);
  98.     parent[startKey] = startKey;
  99.     moveTaken[startKey] = 'S';
  100.     visited.clear();
  101.     visited.insert(startKey);
  102.  
  103.     while(!open.empty()){
  104.         PQItem cur = open.top(); open.pop();
  105.         uint32_t curPacked = packKey(cur.pr,cur.pc,cur.br,cur.bc,cur.pushed);
  106.         // If reached goal
  107.         if(cur.br == goalA.r && cur.bc == goalA.c){
  108.             // reconstruct path by following parent until startKey
  109.             string path;
  110.             uint32_t k = curPacked;
  111.             while(parent[k] != k){
  112.                 char mv = moveTaken[k];
  113.                 path.push_back(mv);
  114.                 k = parent[k];
  115.             }
  116.             reverse(path.begin(), path.end());
  117.             return path;
  118.         }
  119.         // Expand neighbors
  120.         for(int k=0;k<4;k++){
  121.             int npr = cur.pr + dr[k];
  122.             int npc = cur.pc + dc[k];
  123.             if(!inb(npr,npc)) continue;
  124.             if(grid[npr][npc] == '#') continue;
  125.             // walking into other boxes not allowed
  126.             if(!(npr==cur.br && npc==cur.bc) && boxMap[npr][npc]) continue;
  127.  
  128.             // If stepping into box cell => attempt push
  129.             if(npr==cur.br && npc==cur.bc){
  130.                 // if we just pushed in previous move, do not allow push again (prevent consecutive pushes)
  131.                 if(cur.pushed) continue;
  132.                 int nbr = cur.br + dr[k];
  133.                 int nbc = cur.bc + dc[k];
  134.                 if(!inb(nbr,nbc)) continue;
  135.                 if(grid[nbr][nbc] == '#') continue;
  136.                 if(boxMap[nbr][nbc]) continue; // cannot push into another box
  137.                 // cannot push into opponent goal
  138.                 if(nbr==goalB.r && nbc==goalB.c) continue;
  139.                 // avoid dead corner unless it's our goal
  140.                 if(isDeadCorner[nbr][nbc] && !(nbr==goalA.r && nbc==goalA.c)) continue;
  141.                 uint32_t nk = packKey(npr,npc,nbr,nbc,1);
  142.                 if(visited.count(nk)) continue;
  143.                 visited.insert(nk);
  144.                 int ng = cur.g + 1;
  145.                 int nh = manhattan(Pos{nbr,nbc}, goalA)*3 + manhattan(Pos{npr,npc}, Pos{nbr,nbc});
  146.                 parent[nk] = curPacked;
  147.                 moveTaken[nk] = mvChar[k];
  148.                 open.push({npr,npc,nbr,nbc,ng,nh,1});
  149.             } else {
  150.                 // just move (no push)
  151.                 uint32_t nk = packKey(npr,npc,cur.br,cur.bc,0);
  152.                 if(visited.count(nk)) continue;
  153.                 visited.insert(nk);
  154.                 int ng = cur.g + 1;
  155.                 int nh = manhattan(Pos{cur.br,cur.bc}, goalA)*3 + manhattan(Pos{npr,npc}, Pos{cur.br,cur.bc});
  156.                 parent[nk] = curPacked;
  157.                 moveTaken[nk] = mvChar[k];
  158.                 open.push({npr,npc,cur.br,cur.bc,ng,nh,0});
  159.             }
  160.         }
  161.     }
  162.     return "";
  163. }
  164.  
  165. string aStar_noPushed(const Pos &startP, const Pos &startB, const vector<vector<char>> &boxMap){
  166.     // fallback typical A* (no pushed state)
  167.     // implement quick A* similar but without pushed flag
  168.     struct Item { int pr,pc,br,bc; int g,h; };
  169.     struct Cmp { bool operator()(Item const& a, Item const& b) const { return a.g+a.h > b.g+b.h; } };
  170.     priority_queue<Item, vector<Item>, Cmp> open;
  171.     unordered_set<uint32_t> visited;
  172.     unordered_map<uint32_t,uint32_t> parent;
  173.     unordered_map<uint32_t,char> moveTaken;
  174.  
  175.     auto pack2 = [&](int pr,int pc,int br,int bc)->uint32_t{
  176.         return packKey(pr,pc,br,bc,0);
  177.     };
  178.  
  179.     open.push({startP.r,startP.c,startB.r,startB.c,0, manhattan(startB,goalA)*3 });
  180.     uint32_t sK = pack2(startP.r,startP.c,startB.r,startB.c);
  181.     parent[sK] = sK;
  182.     visited.insert(sK);
  183.  
  184.     while(!open.empty()){
  185.         Item cur = open.top(); open.pop();
  186.         if(cur.br == goalA.r && cur.bc == goalA.c){
  187.             string path;
  188.             uint32_t k = pack2(cur.pr,cur.pc,cur.br,cur.bc);
  189.             while(parent[k] != k){
  190.                 path.push_back(moveTaken[k]);
  191.                 k = parent[k];
  192.             }
  193.             reverse(path.begin(), path.end());
  194.             return path;
  195.         }
  196.         for(int k=0;k<4;k++){
  197.             int npr = cur.pr + dr[k], npc = cur.pc + dc[k];
  198.             if(!inb(npr,npc) || grid[npr][npc]=='#') continue;
  199.             if(!(npr==cur.br && npc==cur.bc) && boxMap[npr][npc]) continue;
  200.             // push case
  201.             if(npr==cur.br && npc==cur.bc){
  202.                 int nbr = cur.br + dr[k], nbc = cur.bc + dc[k];
  203.                 if(!inb(nbr,nbc) || grid[nbr][nbc]=='#') continue;
  204.                 if(boxMap[nbr][nbc]) continue;
  205.                 if(nbr==goalB.r && nbc==goalB.c) continue;
  206.                 if(isDeadCorner[nbr][nbc] && !(nbr==goalA.r && nbc==goalA.c)) continue;
  207.                 uint32_t nk = pack2(npr,npc,nbr,nbc);
  208.                 if(visited.count(nk)) continue;
  209.                 visited.insert(nk);
  210.                 parent[nk] = pack2(cur.pr,cur.pc,cur.br,cur.bc);
  211.                 moveTaken[nk] = mvChar[k];
  212.                 open.push({npr,npc,nbr,nbc,cur.g+1, manhattan(Pos{nbr,nbc},goalA)*3});
  213.             } else {
  214.                 uint32_t nk = pack2(npr,npc,cur.br,cur.bc);
  215.                 if(visited.count(nk)) continue;
  216.                 visited.insert(nk);
  217.                 parent[nk] = pack2(cur.pr,cur.pc,cur.br,cur.bc);
  218.                 moveTaken[nk] = mvChar[k];
  219.                 open.push({npr,npc,cur.br,cur.bc,cur.g+1, manhattan(Pos{cur.br,cur.bc},goalA)*3 + manhattan(Pos{npr,npc}, Pos{cur.br,cur.bc})});
  220.             }
  221.         }
  222.     }
  223.     return "";
  224. }
  225.  
  226. int main(){
  227.     ios::sync_with_stdio(false);
  228.     cin.tie(nullptr);
  229.  
  230.     // Read input
  231.     if(!(cin >> R)) { cout << "S\n"; return 0; }
  232.     grid.resize(R);
  233.     for(int i=0;i<R;i++){
  234.         cin >> grid[i];
  235.     }
  236.     cin >> myPos.r >> myPos.c;
  237.     cin >> oppPos.r >> oppPos.c;
  238.  
  239.     // find goals and boxes
  240.     boxes.clear();
  241.     for(int r=0;r<R;r++) for(int c=0;c<C;c++){
  242.         if(grid[r][c]=='A') goalA = {r,c};
  243.         if(grid[r][c]=='B') goalB = {r,c};
  244.         if(grid[r][c]=='X') boxes.push_back({r,c});
  245.     }
  246.  
  247.     // precompute dead corners
  248.     computeDeadCorners();
  249.  
  250.     // build box map for fast checks
  251.     vector<vector<char>> boxMap(R, vector<char>(C,0));
  252.     for(auto &b: boxes) boxMap[b.r][b.c] = 1;
  253.  
  254.     // filter candidate boxes: not dead corner & small Manhattan thresholds
  255.     vector<pair<int,Pos>> cand;
  256.     for(auto &b: boxes){
  257.         if(isDeadCorner[b.r][b.c] && !(b==goalA)) continue;
  258.         int d = manhattan(myPos,b);
  259.         // loosen threshold a bit for optimal variant
  260.         if(d > 50) continue;
  261.         cand.push_back({d,b});
  262.     }
  263.     sort(cand.begin(), cand.end(), [](auto &a, auto &b){ return a.first < b.first; });
  264.  
  265.     string bestPath="";
  266.     // Try each candidate with the better planner (pushed flag)
  267.     for(auto &pr: cand){
  268.         Pos box = pr.second;
  269.         // run A* with pushed-in-state
  270.         string path = aStar_withPushed(myPos, box, boxMap);
  271.         if(!path.empty()){
  272.             bestPath = path;
  273.             break;
  274.         }
  275.     }
  276.  
  277.     // fallback: try faster A* if optimal didn't find anything
  278.     if(bestPath.empty()){
  279.         for(auto &pr: cand){
  280.             Pos box = pr.second;
  281.             string path = aStar_noPushed(myPos, box, boxMap);
  282.             if(!path.empty()){
  283.                 bestPath = path;
  284.                 break;
  285.             }
  286.         }
  287.     }
  288.  
  289.     if(!bestPath.empty()){
  290.         cout << bestPath[0] << "\n";
  291.         return 0;
  292.     }
  293.  
  294.     // no plan -> random legal move
  295.     vector<int> dirs = {0,1,2,3};
  296.     random_shuffle(dirs.begin(), dirs.end());
  297.     for(int k: dirs){
  298.         int nr = myPos.r + dr[k], nc = myPos.c + dc[k];
  299.         if(inb(nr,nc) && grid[nr][nc] != '#' && !boxMap[nr][nc]){
  300.             cout << mvChar[k] << "\n";
  301.             return 0;
  302.         }
  303.     }
  304.     cout << "S\n";
  305.     return 0;
  306. }
  307.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
S
https://ideone.com/RxmM55
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!