fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. using ll = long long;
  6. using pii = pair<int,int>;
  7.  
  8. const int dx[] = {-1,1,0,0};
  9. const int dy[] = {0,0,-1,1};
  10.  
  11. const ll mod = 1e9 + 7;
  12. const ll base = 31;
  13. const ll X = 1;
  14. const ll XX = 5;
  15. const ll XXX = 4;
  16. const int N_boxes = 10;
  17. const int N = 32;
  18. const ll X1 = 3000;
  19. const ll X2 = 1;
  20. const ll X3 = 1;
  21. const ll CANT = 10000;
  22.  
  23. const int inf = 1e9 + 7;
  24.  
  25. const char Box = 'x';
  26. const char You = 'a';
  27. const char Goal = 'A';
  28. const char Wall = '#';
  29. const int BEAM_WIDTH = 150000;
  30.  
  31. const int h[17][17] =  {
  32.     {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  33.     {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53},
  34.     {0,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131},
  35.     {0,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223},
  36.     {0,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311},
  37.     {0,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409},
  38.     {0,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503},
  39.     {0,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613},
  40.     {0,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719},
  41.     {0,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827},
  42.     {0,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941},
  43.     {0,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049},
  44.     {0,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163},
  45.     {0,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283},
  46.     {0,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423},
  47.     {0,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511},
  48.     {0,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619},
  49. };
  50.  
  51. const int h1[17][17] = {
  52.     {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  53.     {0,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747},
  54.     {0,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877},
  55.     {0,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003},
  56.     {0,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129},
  57.     {0,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267},
  58.     {0,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377},
  59.     {0,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503},
  60.     {0,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657},
  61.     {0,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741},
  62.     {0,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861},
  63.     {0,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011},
  64.     {0,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167},
  65.     {0,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301},
  66.     {0,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413},
  67.     {0,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541},
  68.     {0,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671},
  69. };
  70.  
  71. ll Mul(ll x, ll y){
  72.     return x * y % mod;
  73. }
  74.  
  75. ll Add(ll x, ll y){
  76.     x += y;
  77.     if(x >= mod) x -= mod;
  78.     return x;
  79. }
  80.  
  81. ll hx[N_boxes], hy[N_boxes];
  82. pii goal, St;
  83. int Cur = 0;
  84. vector<pii> GvB;
  85. int n, m;
  86. string a[N];
  87. unordered_map<ll,ll> mp;
  88. int Time;
  89.  
  90. const int nigaco1 = 1, nigaco2 = 1; // he so
  91. int niga1 [17] [17], niga2 [17] [17], nigatmp [17] [17];
  92. pii nigadj [] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  93. queue <pii> nigaq;
  94. const int nigalim = 1e9;
  95. void nigafs (pii x, int type) {
  96.     memset (nigatmp, 0x3f, sizeof nigatmp);
  97.     nigatmp [x. fi] [x. se] = 0;
  98.     nigaq. push (x);
  99.     while (!nigaq. empty ()) {
  100.         pii nigabruh = nigaq. front ();
  101.         nigaq. pop ();
  102.         for (pii nigai : nigadj) {
  103.             pii nigane = {nigabruh. fi + nigai. fi, nigabruh. se + nigai. se};
  104.             if (nigane. fi <= 0 || nigane. fi > 16 || nigane. se <= 0 || nigane. se > 16 || a [nigane. fi] [nigane. se] == '#') continue;
  105.             if (nigatmp [nigane. fi] [nigane. se] > nigatmp [nigabruh. fi] [nigabruh. se] + 1) {
  106.                 nigatmp [nigane. fi] [nigane. se] > nigatmp [nigabruh. fi] [nigabruh. se] + 1;
  107.                 nigaq. push (nigane);
  108.             }
  109.         }
  110.     }
  111.     for (int i = 0; i < 16; i ++) for (int j = 0; j < 16; j ++) {
  112.         switch (type) {
  113.         case 1 :
  114.             niga1 [i] [j] += nigatmp [i] [j];
  115.             break;
  116.         case 2 :
  117.             niga2 [i] [j] += nigatmp [i] [j];
  118.             break;
  119.         }
  120.     }
  121. }
  122.  
  123. struct State{
  124.     pii player;
  125.     vector<pii> boxes;
  126.  
  127. //    int cost;
  128.     ll cost_heu;
  129.     int cur;
  130.  
  131.     string path;
  132.  
  133.     State(pii _player, vector<pii> _boxes, int _cur, string _path = "")
  134.         : player(_player), boxes(_boxes), cur(_cur), path(_path) {
  135.         cost_heu = cost_H();
  136.     }
  137.  
  138.     ll Hash() const {
  139.         ll res = 1;
  140.         for(pii i : boxes) res = Mul(res,h[i.fi][i.se]);
  141.         res = Mul(res,h1[player.fi][player.se]);
  142.         return res;
  143.     }
  144.     ll cost_H() const{
  145.         ll res = 0;
  146.         int res1 = inf;
  147.         int res2 = inf;
  148.         for(pii i : boxes){
  149.             if(a[i.fi][i.se] != Goal){
  150.                 res = res + abs(i.fi - goal.fi) + abs(i.se - goal.se);
  151.                 res1 = min(res1,abs(i.fi - player.fi) + abs(i.se - player.se));
  152.                 res2 = min(res2,abs(i.fi - goal.fi) + abs(i.se - goal.se));
  153.             }
  154.         }
  155.         //return res;
  156.         return X * res + XX * (res1 == inf ? 0 : res1) + XXX * (res2 == inf ? 0 : res2);
  157.     }
  158.  
  159.     ll real_cost() const{
  160.         return X2 * cost_heu - X1 * cur;
  161.     }
  162.  
  163.     bool operator < (const State&other) const{
  164.         return real_cost() > other.real_cost();
  165.     }
  166.  
  167. };
  168.  
  169.  
  170. bool chk_in(int x, int y){
  171.     return (1 <= x && x <= n && 1 <= y && y <= m);
  172. }
  173.  
  174. void out(State x){
  175.     cout << "Player at :" << x.player.fi << ' ' << x.player.se << "\n";
  176.     cout << "Cost :" << ' ' << x.cost_heu << ' ' << x.cur << "\n";
  177.     cout << "Boxes:\n";
  178.     int dem = 0;
  179.     for(pii i : x.boxes) {
  180.         dem++;
  181.         cout << "Boxes " <<dem <<":" <<i.fi << ' ' << i.se << "\n";
  182.     }
  183.     cout << "Hash:" << x.Hash();
  184.     cout << "\n";
  185. }
  186.  
  187. void sol(){
  188.     cin >> Time;
  189.     n = 15; m = 15;
  190.  
  191.  
  192.     for(int i = 0 ; i <= m ; ++i)
  193.         a[0][i] = a[n + 1][i] = '#';
  194.  
  195.     for(int i = 1 ; i <= n ; ++i){
  196.         cin >> a[i];
  197.         a[i] = '#' + a[i] + '#';
  198.         for(int j = 1 ; j <= m ; ++j){
  199.             if(a[i][j] == Box) {GvB.push_back({i,j});Cur++;}
  200.             if(a[i][j] == Goal) goal = {i,j};
  201.             if(a[i][j] == You) St = {i,j};
  202.         }
  203.     }
  204.  
  205.     for (auto i : GvB) {
  206.         nigafs (i, 1);
  207.     }
  208.     nigafs (goal, 2);
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.     int ans = 0;
  221.  
  222.     cout << Cur << "!\n";
  223.     State orgin = State(St,GvB,0,"");
  224.     vector<State> beam{orgin};
  225.     mp[orgin.Hash()] = orgin.real_cost();
  226.     ll mn = orgin.real_cost();
  227.     for(int step = 0; step < Time && !beam.empty(); ++step){
  228.         vector<State> nxt_beam;
  229.         nxt_beam.reserve(beam.size() * 4);
  230. ////
  231.         for(auto &t : beam){
  232.             ans = max(ans,t.cur);
  233.             if(ans == Cur) break;
  234.             if(t.real_cost() != mp[t.Hash()]) continue;
  235.             mn = min(mn,t.real_cost());
  236.             for(int j = 0 ; j < 4 ; ++j){
  237.  
  238.                 int _x = t.player.fi + dx[j];
  239.                 int _y = t.player.se + dy[j];
  240.                 if(!chk_in(_x,_y)) continue;
  241.                 int _x1 = _x + dx[j];
  242.                 int _y1 = _y + dy[j];
  243.  
  244.                 int pos = -1;
  245.                 int pos1 = -1;
  246.                 for(int _j = 0 ; _j < (int)t.boxes.size() ; ++_j){
  247.                     if(a[_x][_y] != Goal){
  248.                     if(_x == t.boxes[_j].fi && _y == t.boxes[_j].se) pos = _j;
  249.                     }
  250.                     if(a[_x1][_y1] != Goal){
  251.                     if(_x1 == t.boxes[_j].fi && _y1 == t.boxes[_j].se) pos1 = _j;
  252.                     }
  253.                 }
  254.  
  255.                 if(pos != -1 && pos1 != -1) continue;
  256.                 if(pos != -1 && a[_x1][_y1] == '#') continue;
  257.                 State _new = t;
  258.                 _new.player = {_x,_y};
  259.                 if(pos != -1) {_new.boxes[pos] = {_x1,_y1};
  260.                 if(a[_x1][_y1] == Goal) _new.cur += 1;
  261.                 }
  262.                 _new.cost_heu = _new.cost_H();
  263.                 ll hval = _new.Hash();
  264.                 if(_new.cost_heu >= mn + CANT) continue;
  265.                 if(mp.count(hval) && mp[hval] <= _new.real_cost()) {
  266.                     continue;
  267.                 }
  268.  
  269.                 mp[hval] = _new.real_cost();
  270.                 nxt_beam.push_back(_new);
  271.             }
  272.         }
  273.         if(ans == Cur) break;
  274.         sort(nxt_beam.begin(),nxt_beam.end());
  275.         while((int)nxt_beam.size() > BEAM_WIDTH) nxt_beam.pop_back();
  276.         beam.swap(nxt_beam);
  277.     }
  278.     cout << ans << "\n";
  279. }
  280.  
  281. int main(){
  282. //    freopen ("input.txt", "r", stdin);
  283. //    freopen ("output.txt", "w", stdout);
  284.     int tc;
  285.     tc = 1;
  286.     while(tc--) sol();
  287.  
  288.     return 0;
  289. }
  290.  
  291.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0!
0
https://ideone.com/ShsLkZ
language:
C++14 (gcc 8.3)
created:
6 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!