#include <iostream> #include <string.h> #include <unordered_set> using namespace std; union long2int { long long ll; int i[2]; }; long long encode(const int x, const int y) { long2int l2i; l2i.i[0] = x; l2i.i[1] = y; return l2i.ll; } void decode(const long long ll, int &x, int &y) { long2int l2i; l2i.ll = ll; x = l2i.i[0]; y = l2i.i[1]; } // visited states unordered_set<long long> visited; // go backwards to unsivited states void backwards(long long pos, unordered_set<long long> &positions) { int v, x; decode(pos, v, x); for (int d=-1; d<=+1; d++) { long long b = encode(v+d, x-v); if (!visited.count(b)) { positions.insert(b); } } } // A360926 Smallest number of moves needed to win Integer Lunar Lander with a starting position of (n,n). #define MAX 251 int a[MAX]; int main() { memset(a, -1, sizeof(a)); int u=0; // positions at distance n unordered_set<long long> w; w.insert(0); for (int n=0;; n++) { // set everything as seen for (long long pos : w) { visited.insert(pos); int v, x; decode(pos, v,x); if (x==0 && v>=0 && v<MAX) { a[v] = n; } } while (a[u]>=0) { cout << u << ' ' << a[u] << endl; u++; if (u==MAX) { goto theEnd; } } // go backwards unordered_set<long long> before; for (long long pos : w) { backwards(pos, before); } w = before; } theEnd: return 0; }