fork download 
  1. // me.cpp -- C++14
  2. // Compile: g++ -std=c++14 me.cpp -O2 -o me.exe
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. struct Pos { int r, c; };
  7. const int MAXN = 32;
  8. int N;
  9. int dr[4] = {-1,1,0,0};
  10. int dc[4] = {0,0,-1,1};
  11. char mvChar[4] = {'U','D','L','R'};
  12.  
  13. bool inb(int r,int c){ return r>=0 && r<N && c>=0 && c<N; }
  14.  
  15. string state_key(const vector<pair<int,int>>& boxes, const Pos &player){
  16.     // boxes must be sorted externally
  17.     string s;
  18.     for(size_t i=0;i<boxes.size();++i){
  19.         s += to_string(boxes[i].first) + "," + to_string(boxes[i].second) + ";";
  20.     }
  21.     s += "|" + to_string(player.r) + "," + to_string(player.c);
  22.     return s;
  23. }
  24.  
  25. vector<vector<int>> bfs_from_goals(const vector<string>& grid, const vector<Pos>& goals){
  26.     vector<vector<int>> dist(N, vector<int>(N, -1));
  27.     queue<Pos> q;
  28.     for(auto &g: goals){
  29.         dist[g.r][g.c] = 0;
  30.         q.push(g);
  31.     }
  32.     while(!q.empty()){
  33.         Pos u = q.front(); q.pop();
  34.         for(int d=0; d<4; ++d){
  35.             int nr = u.r + dr[d], nc = u.c + dc[d];
  36.             if(!inb(nr,nc)) continue;
  37.             if(grid[nr][nc] == '#') continue;
  38.             if(dist[nr][nc] != -1) continue;
  39.             dist[nr][nc] = dist[u.r][u.c] + 1;
  40.             q.push({nr,nc});
  41.         }
  42.     }
  43.     return dist;
  44. }
  45.  
  46. vector<vector<int>> player_reachable(const vector<string>& grid, const vector<pair<int,int>>& boxes, const Pos &start){
  47.     vector<vector<int>> vis(N, vector<int>(N,0));
  48.     vector<vector<int>> blocked(N, vector<int>(N,0));
  49.     for(auto &b: boxes) blocked[b.first][b.second]=1;
  50.     queue<Pos> q;
  51.     if(!blocked[start.r][start.c]){
  52.         vis[start.r][start.c]=1;
  53.         q.push(start);
  54.     }
  55.     while(!q.empty()){
  56.         Pos u = q.front(); q.pop();
  57.         for(int d=0; d<4; ++d){
  58.             int nr=u.r+dr[d], nc=u.c+dc[d];
  59.             if(!inb(nr,nc)) continue;
  60.             if(vis[nr][nc]) continue;
  61.             if(grid[nr][nc]=='#') continue;
  62.             if(blocked[nr][nc]) continue;
  63.             vis[nr][nc]=1;
  64.             q.push({nr,nc});
  65.         }
  66.     }
  67.     // return visited as ints (0/1)
  68.     return vis;
  69. }
  70.  
  71. // BFS path (no box move) to target cell; returns next step from start (dr,dc) index or -1 if unreachable
  72. int next_step_towards(const vector<string>& grid, const vector<pair<int,int>>& boxes, const Pos &start, const Pos &target){
  73.     vector<vector<int>> blocked(N, vector<int>(N,0));
  74.     for(auto &b: boxes) blocked[b.first][b.second]=1;
  75.     vector<vector<int>> dist(N, vector<int>(N,-1));
  76.     vector<vector<pair<int,int>>> pre(N, vector<pair<int,int>>(N, {-1,-1}));
  77.     queue<Pos> q;
  78.     if(blocked[start.r][start.c]) return -1;
  79.     dist[start.r][start.c]=0;
  80.     q.push(start);
  81.     while(!q.empty()){
  82.         Pos u = q.front(); q.pop();
  83.         if(u.r==target.r && u.c==target.c) break;
  84.         for(int d=0; d<4; ++d){
  85.             int nr=u.r+dr[d], nc=u.c+dc[d];
  86.             if(!inb(nr,nc)) continue;
  87.             if(blocked[nr][nc]) continue;
  88.             if(grid[nr][nc]=='#') continue;
  89.             if(dist[nr][nc]!=-1) continue;
  90.             dist[nr][nc] = dist[u.r][u.c] + 1;
  91.             pre[nr][nc] = make_pair(u.r,u.c);
  92.             q.push({nr,nc});
  93.         }
  94.     }
  95.     if(dist[target.r][target.c]==-1) return -1;
  96.     // backtrack to find first step
  97.     int tr = target.r, tc = target.c;
  98.     while(!(pre[tr][tc].first == start.r && pre[tr][tc].second == start.c)){
  99.         auto p = pre[tr][tc];
  100.         tr = p.first; tc = p.second;
  101.     }
  102.     for(int d=0; d<4; ++d){
  103.         if(start.r + dr[d] == tr && start.c + dc[d] == tc) return d;
  104.     }
  105.     return -1;
  106. }
  107.  
  108. int main(){
  109.     ios::sync_with_stdio(false);
  110.     cin.tie(nullptr);
  111.  
  112.     // Read input from server
  113.     if(!(cin >> N)) { cout << "S\n"; return 0; }
  114.     vector<string> grid(N);
  115.     for(int i=0;i<N;++i) cin >> grid[i];
  116.     Pos me, opp;
  117.     cin >> me.r >> me.c;
  118.     cin >> opp.r >> opp.c;
  119.  
  120.     // collect boxes and goals
  121.     vector<pair<int,int>> boxes;
  122.     vector<Pos> myGoals;
  123.     for(int r=0;r<N;++r) for(int c=0;c<N;++c){
  124.         if(grid[r][c]=='X') boxes.emplace_back(r,c);
  125.         if(grid[r][c]=='A') myGoals.push_back({r,c});
  126.     }
  127.  
  128.     // If already any box on goal -> do nothing
  129.     for(auto &b: boxes){
  130.         for(auto &g: myGoals) if(b.first==g.r && b.second==g.c){
  131.             cout << "S\n";
  132.             return 0;
  133.         }
  134.     }
  135.  
  136.     if(myGoals.empty()){
  137.         // no goal for me -> stand
  138.         cout << "S\n";
  139.         return 0;
  140.     }
  141.  
  142.     // Precompute dist-to-goal (ignoring boxes)
  143.     vector<vector<int>> distToGoal = bfs_from_goals(grid, myGoals);
  144.  
  145.     // If no box can reach goal (dist INF) -> fallback BFS towards nearest box
  146.     bool anyBoxReachable=false;
  147.     for(auto &b: boxes){
  148.         if(distToGoal[b.first][b.second] != -1) { anyBoxReachable=true; break; }
  149.     }
  150.  
  151.     // A* on pushes: state = (sorted boxes positions, player pos)
  152.     // heuristic: min distToGoal over boxes (admissible)
  153.     struct ANode {
  154.         vector<pair<int,int>> boxes;
  155.         Pos player;
  156.         int g;
  157.         int h;
  158.         bool operator>(ANode const& o) const { return g + h > o.g + o.h; }
  159.     };
  160.  
  161.     auto heuristic = [&](const vector<pair<int,int>>& bs)->int{
  162.         int mn = INT_MAX;
  163.         for(auto &b: bs){
  164.             int d = distToGoal[b.first][b.second];
  165.             if(d==-1) continue;
  166.             mn = min(mn, d);
  167.         }
  168.         if(mn==INT_MAX) return 1000000;
  169.         return mn;
  170.     };
  171.  
  172.     // Sort initial boxes for canonical state representation
  173.     sort(boxes.begin(), boxes.end());
  174.     string start_key = state_key(boxes, me);
  175.  
  176.     // Priority queue
  177.     priority_queue<ANode, vector<ANode>, greater<ANode>> pq;
  178.     unordered_map<string, pair<string, string> > parent; // child_key -> (parent_key, action)
  179.     // action format: "push:idx:dir" where idx is index in boxes vector before push, dir 0..3
  180.     unordered_map<string, int> gscore;
  181.     string init_key = start_key;
  182.     int init_h = heuristic(boxes);
  183.     pq.push(ANode{boxes, me, 0, init_h});
  184.     gscore[init_key] = 0;
  185.     parent[init_key] = make_pair(string(""), string("")); // root marker
  186.  
  187.     string goal_state_key = "";
  188.     bool found = false;
  189.     int expansions = 0;
  190.     const int MAX_EXPAND = 200000; // safety limit
  191.  
  192.     while(!pq.empty() && expansions < MAX_EXPAND){
  193.         ANode cur = pq.top(); pq.pop();
  194.         string cur_key = state_key(cur.boxes, cur.player);
  195.         int cur_g = cur.g;
  196.         // skip stale
  197.         if(gscore.find(cur_key) != gscore.end() && cur_g != gscore[cur_key]) continue;
  198.         expansions++;
  199.  
  200.         // check goal: any box on a goal cell
  201.         bool ok=false;
  202.         for(auto &b: cur.boxes){
  203.             if(distToGoal[b.first][b.second]==0){ ok=true; break; }
  204.             // more generally box directly on any myGoal
  205.             for(auto &mg: myGoals) if(b.first==mg.r && b.second==mg.c) { ok=true; break; }
  206.             if(ok) break;
  207.         }
  208.         if(ok){
  209.             goal_state_key = cur_key;
  210.             found = true;
  211.             break;
  212.         }
  213.  
  214.         // compute player's reachable area without moving boxes
  215.         vector<vector<int>> reachable = player_reachable(grid, cur.boxes, cur.player);
  216.  
  217.         // For each box and each direction, attempt push
  218.         for(size_t bi=0; bi<cur.boxes.size(); ++bi){
  219.             int br = cur.boxes[bi].first;
  220.             int bc = cur.boxes[bi].second;
  221.             for(int d=0; d<4; ++d){
  222.                 int from_r = br - dr[d];
  223.                 int from_c = bc - dc[d];
  224.                 int to_r = br + dr[d];
  225.                 int to_c = bc + dc[d];
  226.                 if(!inb(from_r,from_c) || !inb(to_r,to_c)) continue;
  227.                 // target cell for box must be free (not wall, not another box)
  228.                 if(grid[to_r][to_c] == '#') continue;
  229.                 bool occupied = false;
  230.                 for(size_t j=0;j<cur.boxes.size();++j){
  231.                     if(j==bi) continue;
  232.                     if(cur.boxes[j].first==to_r && cur.boxes[j].second==to_c){ occupied=true; break; }
  233.                 }
  234.                 if(occupied) continue;
  235.                 // player must be able to reach from_r,from_c without moving boxes
  236.                 if(!reachable[from_r][from_c]) continue;
  237.                 // we can push: create new boxes vector and new player pos = br,bc (where box was)
  238.                 vector<pair<int,int>> new_boxes = cur.boxes;
  239.                 new_boxes[bi] = make_pair(to_r,to_c);
  240.                 sort(new_boxes.begin(), new_boxes.end());
  241.                 Pos new_player = { br, bc };
  242.                 int new_g = cur_g + 1; // cost per push = 1 (we optimize pushes)
  243.                 int new_h = heuristic(new_boxes);
  244.                 string new_key = state_key(new_boxes, new_player);
  245.                 if(gscore.find(new_key) == gscore.end() || new_g < gscore[new_key]){
  246.                     gscore[new_key] = new_g;
  247.                     parent[new_key] = make_pair(cur_key, string("push:") + to_string(br) + "," + to_string(bc) + ":" + to_string(d));
  248.                     pq.push(ANode{new_boxes, new_player, new_g, new_h});
  249.                 }
  250.             }
  251.         }
  252.     } // end A*
  253.  
  254.     // reconstruct sequence of pushes (if found)
  255.     vector<string> actions; // actions from start -> goal
  256.     vector<pair<vector<pair<int,int>>, Pos>> states_seq; // optional
  257.     if(found){
  258.         string k = goal_state_key;
  259.         while(parent[k].first != ""){
  260.             actions.push_back(parent[k].second);
  261.             k = parent[k].first;
  262.         }
  263.         reverse(actions.begin(), actions.end());
  264.         // Now we have a sequence of pushes; need to convert into atomic moves:
  265.         // For each push action "push:br,bc:d", the player must first walk from current pos to (from = br - dr[d], bc - dc[d])
  266.         // then perform push (one atomic move in direction d). We'll compute the first atomic move to output.
  267.         vector<pair<int,int>> cur_boxes = boxes;
  268.         Pos cur_player = me;
  269.         for(size_t ai=0; ai<actions.size(); ++ai){
  270.             string s = actions[ai]; // format "push:br,bc:d"
  271.             // parse
  272.             // push:br,bc:d
  273.             int p1 = s.find(":");
  274.             int p2 = s.find(":", p1+1);
  275.             string mid = s.substr(p1+1, p2 - (p1+1));
  276.             int dd = stoi(s.substr(p2+1));
  277.             int comma = mid.find(",");
  278.             int br = stoi(mid.substr(0,comma));
  279.             int bc = stoi(mid.substr(comma+1));
  280.             int from_r = br - dr[dd];
  281.             int from_c = bc - dc[dd];
  282.             // if currently adjacent and in correct position -> push now
  283.             if(cur_player.r == from_r && cur_player.c == from_c){
  284.                 // push is atomic move - return push direction
  285.                 cout << mvChar[dd] << "\n";
  286.                 return 0;
  287.             }
  288.             // else find path step from cur_player to from_{r,c} avoiding boxes (current cur_boxes)
  289.             int step = next_step_towards(grid, cur_boxes, cur_player, {from_r, from_c});
  290.             if(step != -1){
  291.                 cout << mvChar[step] << "\n";
  292.                 return 0;
  293.             } else {
  294.                 // unreachable to the required pushing square (shouldn't happen if A* used reachability)
  295.                 // try a fallback: go towards nearest box step
  296.                 break;
  297.             }
  298.         }
  299.         // If code reaches here, somehow we couldn't output a step from plan -> fallback below
  300.     }
  301.  
  302.     // Fallback strategies
  303.     // 1) If A* didn't find plan or we couldn't follow plan, step towards nearest box (BFS).
  304.     // Find nearest box cell we can walk to (adjacent to box) and output one step toward it.
  305.     // Build blocked map
  306.     vector<vector<int>> blocked(N, vector<int>(N,0));
  307.     for(auto &b: boxes) blocked[b.first][b.second]=1;
  308.     // target positions are any cell adjacent to a box and walkable
  309.     vector<vector<int>> dist(N, vector<int>(N,-1));
  310.     vector<vector<pair<int,int>>> pre(N, vector<pair<int,int>>(N, {-1,-1}));
  311.     queue<Pos> q;
  312.     if(!blocked[me.r][me.c] && grid[me.r][me.c] != '#'){
  313.         dist[me.r][me.c]=0;
  314.         q.push(me);
  315.     }
  316.     Pos chosenTarget = {-1,-1};
  317.     while(!q.empty()){
  318.         Pos u = q.front(); q.pop();
  319.         // check adjacency to any box
  320.         bool adjBox = false;
  321.         for(int d=0; d<4; ++d){
  322.             int nr=u.r+dr[d], nc=u.c+dc[d];
  323.             if(!inb(nr,nc)) continue;
  324.             if(blocked[nr][nc]) { adjBox = true; break; }
  325.         }
  326.         if(adjBox){
  327.             chosenTarget = u;
  328.             break;
  329.         }
  330.         for(int d=0; d<4; ++d){
  331.             int nr=u.r+dr[d], nc=u.c+dc[d];
  332.             if(!inb(nr,nc)) continue;
  333.             if(blocked[nr][nc]) continue;
  334.             if(grid[nr][nc]=='#') continue;
  335.             if(dist[nr][nc] != -1) continue;
  336.             dist[nr][nc] = dist[u.r][u.c] + 1;
  337.             pre[nr][nc] = make_pair(u.r,u.c);
  338.             q.push({nr,nc});
  339.         }
  340.     }
  341.     if(chosenTarget.r == -1){
  342.         // cannot reach any adjacent-to-box cell: stand
  343.         cout << "S\n";
  344.         return 0;
  345.     } else {
  346.         // backtrack next step
  347.         int tr = chosenTarget.r, tc = chosenTarget.c;
  348.         while(!(pre[tr][tc].first == me.r && pre[tr][tc].second == me.c) && !(tr==me.r && tc==me.c)){
  349.             auto p = pre[tr][tc];
  350.             tr = p.first; tc = p.second;
  351.         }
  352.         if(tr==me.r && tc==me.c){
  353.             // we are already at chosenTarget, but it's adjacent to box. just stay or push if possible
  354.             // choose push if adjacent box and push destination empty
  355.             for(int d=0; d<4; ++d){
  356.                 int br = me.r + dr[d], bc = me.c + dc[d];
  357.                 if(!inb(br,bc)) continue;
  358.                 if(!blocked[br][bc]) continue;
  359.                 int trr = br + dr[d], tcc = bc + dc[d];
  360.                 if(!inb(trr,tcc)) continue;
  361.                 if(grid[trr][tcc]=='#') continue;
  362.                 bool occ=false;
  363.                 for(auto &b: boxes) if(b.first==trr && b.second==tcc) { occ=true; break; }
  364.                 if(occ) continue;
  365.                 // push
  366.                 cout << mvChar[d] << "\n";
  367.                 return 0;
  368.             }
  369.             // otherwise stand
  370.             cout << "S\n";
  371.             return 0;
  372.         } else {
  373.             // find direction from me -> (tr,tc)
  374.             for(int d=0; d<4; ++d){
  375.                 if(me.r + dr[d] == tr && me.c + dc[d] == tc){
  376.                     cout << mvChar[d] << "\n";
  377.                     return 0;
  378.                 }
  379.             }
  380.         }
  381.     }
  382.  
  383.     // ultimate fallback
  384.     cout << "S\n";
  385.     return 0;
  386. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
S
https://ideone.com/qYBiHV
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!