Language: C++

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>




using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);




#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))




template <class T>
inline bool chmin(T &lhs, const T &rhs) {
&#160; if (rhs < lhs) {
&#160; &#160; lhs = rhs;
&#160; &#160; return true;
&#160; }
&#160; return false;
}
template <class T>
inline bool chmax(T &lhs, const T &rhs) {
&#160; if (lhs < rhs) {
&#160; &#160; lhs = rhs;
&#160; &#160; return true;
&#160; }
&#160; return false;
}








const int HALF = 10;
const ll BASE = 1e+9 + 7;
int n;
int N;
int posX[15];
int posY[15];
int dist[15][15];
const int dx[4] = { -1, 0, 0, 1 };
const int dy[4] = { -1, -1, 1, 1 };




inline int Encode(int x, int y) {
&#160; assert(x <= y);
&#160; return y * (y + 1) / 2 + x;
}
inline void Decode(int code, int &x, int &y) {
&#160; assert(0 <= code && code < 15);
&#160; x = posX[code];
&#160; y = posY[code];
}




struct State {
&#160; char cost;
&#160; char a;
&#160; char cards[15];
&#160; int Get(int x, int y) {
&#160; &#160; return cards[Encode(x, y)];
&#160; }
&#160; void Set(int x, int y, int v) {
&#160; &#160; cards[Encode(x, y)] = v;
&#160; }
&#160; void Swap(int x1, int y1, int x2, int y2) {
&#160; &#160; swap(cards[Encode(x1, y1)], cards[Encode(x2, y2)]);
&#160; }
&#160; void Holl(int &rx, int &ry) {
&#160; &#160; REP(i, N) {
&#160; &#160; &#160; if (cards[i] == 1) {
&#160; &#160; &#160; &#160; rx = posX[i];
&#160; &#160; &#160; &#160; ry = posY[i];
&#160; &#160; &#160; &#160; return;
&#160; &#160; &#160; }
&#160; &#160; }
&#160; &#160; assert(false);
&#160; }
&#160; int HollX() {
&#160; &#160; int x, y;
&#160; &#160; Holl(x, y);
&#160; &#160; return x;
&#160; }
&#160; int HollY() {
&#160; &#160; int x, y;
&#160; &#160; Holl(x, y);
&#160; &#160; return y;
&#160; }
&#160; void CalcA() {
&#160; &#160; int rev[16];
&#160; &#160; REP(i, N) {
&#160; &#160; &#160; rev[(int)cards[i] - 1] = i;
&#160; &#160; }




&#160; &#160; a = 0;
&#160; &#160; FOR(i, 1, N) {
&#160; &#160; &#160; a += dist[rev[i]][i];
&#160; &#160; }
&#160; &#160; FOR(i, 3, N) {
&#160; &#160; &#160; if (cards[i] == i + 1) { continue; }
&#160; &#160; &#160; int fx = posX[i];
&#160; &#160; &#160; int fy = posY[i];
&#160; &#160; &#160; REP(dir, 4) {
&#160; &#160; &#160; &#160; int nx = fx + dx[dir];
&#160; &#160; &#160; &#160; int ny = fy + dy[dir];
&#160; &#160; &#160; &#160; if (nx < 0 || nx > ny || ny < 0 || ny >= n) { continue; }
&#160; &#160; &#160; &#160; if (cards[Encode(nx, ny)] != Encode(nx, ny) + 1) { goto next; }
&#160; &#160; &#160; }
&#160; &#160; &#160; a += 6;
next:;
&#160; &#160; }
&#160; &#160; if (a != 0 && n == 5) {
&#160; &#160; &#160; if (cards[0] == 1 && cards[1] == 2 && cards[2] == 3) {
&#160; &#160; &#160; &#160; a += 6;
&#160; &#160; &#160; }
&#160; &#160; &#160; if ((cards[0] == 1 || cards[1] == 1 || cards[2] == 1) &&
&#160; &#160; &#160; &#160; &#160; (cards[3] == 4 && cards[4] == 5 && cards[5] == 6) &&
&#160; &#160; &#160; &#160; &#160; (cards[6] != 7 || cards[7] != 8 || cards[8] != 9 ||
&#160; &#160; &#160; &#160; &#160; &#160;cards[9] != 10 || cards[11] != 12 || cards[12] != 13 || cards[13] != 14)) {
&#160; &#160; &#160; &#160; a += 6;
&#160; &#160; &#160; }
&#160; &#160; &#160; if ((cards[0] == 1 || cards[1] == 1 || cards[2] == 1 ||
&#160; &#160; &#160; &#160; &#160; &#160;cards[3] == 1 || cards[4] == 1 || cards[5] == 1) &&
&#160; &#160; &#160; &#160; &#160; (cards[6] == 7 || cards[7] == 8 || cards[8] == 9) &&
&#160; &#160; &#160; &#160; &#160; (cards[9] != 10 || cards[11] != 12 || cards[12] != 13 || cards[13] != 14)) {
&#160; &#160; &#160; &#160; a += 6;
&#160; &#160; &#160; }
&#160; &#160; }
&#160; }
&#160; ull Hash() {
&#160; &#160; ll ret = 0;
&#160; &#160; REP(i, N) {
&#160; &#160; &#160; ret = ret * BASE + cards[i];
&#160; &#160; }
&#160; &#160; return ret;
&#160; }
&#160; bool operator<(const State &rhs) const {
&#160; &#160; return cost + a > rhs.cost + rhs.a;
&#160; }
};




int main() {
&#160; REP(y, 5) {
&#160; &#160; REP(x, y + 1) {
&#160; &#160; &#160; posX[Encode(x, y)] = x;
&#160; &#160; &#160; posY[Encode(x, y)] = y;
&#160; &#160; }
&#160; }
&#160; int test_case = 0;
&#160; while (scanf("%d", &n), n) {
&#160; &#160; test_case++;
&#160; &#160; N = n * (n + 1) / 2;




&#160; &#160; // calc dist
&#160; &#160; MEMSET(dist, 0x0f);
&#160; &#160; REP(i, N) { dist[i][i] = 0; }
&#160; &#160; REP(i, N) {
&#160; &#160; &#160; int fx = posX[i];
&#160; &#160; &#160; int fy = posY[i];
&#160; &#160; &#160; REP(dir, 4) {
&#160; &#160; &#160; &#160; int nx = fx + dx[dir];
&#160; &#160; &#160; &#160; int ny = fy + dy[dir];
&#160; &#160; &#160; &#160; if (nx < 0 || nx > ny || ny < 0 || ny >= n) { continue; }
&#160; &#160; &#160; &#160; dist[i][Encode(nx, ny)] = 1;
&#160; &#160; &#160; }
&#160; &#160; }
&#160; &#160; REP(k, N) REP(i, N) REP(j, N) {
&#160; &#160; &#160; dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
&#160; &#160; }




&#160; &#160; // Get Input
&#160; &#160; State ini;
&#160; &#160; ini.cost = 0;
&#160; &#160; REP(y, n) {
&#160; &#160; &#160; REP(x, y + 1) {
&#160; &#160; &#160; &#160; int v;
&#160; &#160; &#160; &#160; scanf("%d", &v);
&#160; &#160; &#160; &#160; ini.Set(x, y, v);
&#160; &#160; &#160; }
&#160; &#160; }
&#160; &#160; if (ini.Get(0, n - 1) != Encode(0, n - 1) + 1) {
&#160; &#160; &#160; ini.Swap(0, n - 1, 0, n - 2);
&#160; &#160; &#160; ini.cost++;
&#160; &#160; }
&#160; &#160; if (ini.Get(n - 1, n - 1) != Encode(n - 1, n - 1) + 1) {
&#160; &#160; &#160; ini.Swap(n - 1, n - 1, n - 2, n - 2);
&#160; &#160; &#160; ini.cost++;
&#160; &#160; }
&#160; &#160; ini.CalcA();
&#160; &#160; int x, y;
&#160; &#160; ini.Holl(x, y);




&#160; &#160; // A*
&#160; &#160; map<ull, int> dists;
&#160; &#160; priority_queue<State> que;
&#160; &#160; que.push(ini);
&#160; &#160; dists[ini.Hash()] = 0;
&#160; &#160; int ans = 45;
&#160; &#160; while (!que.empty()) {
&#160; &#160; &#160; State s = que.top();
&#160; &#160; &#160; que.pop();
&#160; &#160; &#160; if (s.a == 0) {
&#160; &#160; &#160; &#160; //cout << "OK" << endl;
&#160; &#160; &#160; &#160; ans = s.cost;
&#160; &#160; &#160; &#160; break;
&#160; &#160; &#160; }
&#160; &#160; &#160; int hx, hy;
&#160; &#160; &#160; s.Holl(hx, hy);
&#160; &#160; &#160; REP(dir, 4) {
&#160; &#160; &#160; &#160; int nx = hx + dx[dir];
&#160; &#160; &#160; &#160; int ny = hy + dy[dir];
&#160; &#160; &#160; &#160; if (nx < 0 || nx > ny || ny < 0 || ny >= n) { continue; }
&#160; &#160; &#160; &#160; State ns = s;
&#160; &#160; &#160; &#160; ns.Swap(hx, hy, nx, ny);
&#160; &#160; &#160; &#160; ns.cost++;
&#160; &#160; &#160; &#160; ns.CalcA();
&#160; &#160; &#160; &#160; if (ns.cost + ns.a > ans) { continue; }
&#160; &#160; &#160; &#160; ull h = ns.Hash();
&#160; &#160; &#160; &#160; if (dists.count(h) && dists[h] <= ns.cost) { continue; }
&#160; &#160; &#160; &#160; dists[h] = ns.cost;
&#160; &#160; &#160; &#160; que.push(ns);
&#160; &#160; &#160; }
&#160; &#160; }
&#160; &#160; printf("Case %d: %d\n", test_case, ans);
&#160; }
}

Compiler output:
a.cc:37:2: error: stray '#' in program
   37 | &#160; if (rhs < lhs) {
      |  ^
a.cc:38:2: error: stray '#' in program
   38 | &#160; &#160; lhs = rhs;
      |  ^
a.cc:38:9: error: stray '#' in program
   38 | &#160; &#160; lhs = rhs;
      |         ^
a.cc:39:2: error: stray '#' in program
   39 | &#160; &#160; return true;
      |  ^
a.cc:39:9: error: stray '#' in program
   39 | &#160; &#160; return true;
      |         ^
a.cc:40:2: error: stray '#' in program
   40 | &#160; }
      |  ^
a.cc:41:2: error: stray '#' in program
   41 | &#160; return false;
      |  ^
a.cc:45:2: error: stray '#' in program
   45 | &#160; if (lhs < rhs) {
      |  ^
a.cc:46:2: error: stray '#' in program
   46 | &#160; &#160; lhs = rhs;
      |  ^
a.cc:46:9: error: stray '#' in program
   46 | &#160; &#160; lhs = rhs;
      |         ^
a.cc:47:2: error: stray '#' in program
   47 | &#160; &#160; return true;
      |  ^
a.cc:47:9: error: stray '#' in program
   47 | &#160; &#160; return true;
      |         ^
a.cc:48:2: error: stray '#' in program
   48 | &#160; }
      |  ^
a.cc:49:2: error: stray '#' in program
   49 | &#160; return false;
      |  ^
a.cc:73:2: error: stray '#' in program
   73 | &#160; assert(x <= y);
      |  ^
a.cc:74:2: error: stray '#' in program
   74 | &#160; return y * (y + 1) / 2 + x;
      |  ^
a.cc:77:2: error: stray '#' in program
   77 | &#160; assert(0 <= code && code < 15);
      |  ^
a.cc:78:2: error: stray '#' in program
   78 | &#160; x = posX[code];
      |  ^
a.cc:79:2: error: stray '#' in program
   79 | &#160; y = posY[code];
      |  ^
a.cc:86:2: error: stray '#' in program
   86 | &#160; char cost;
      |  ^
a.cc:87:2: error: stray '#' in program
   87 | &#160; char a;
      |  ^
a.cc:88:2: error: stray '#' in program
   88 | &#160; char cards[15];
      |  ^
a.cc:89:2: error: stray '#' in program
   89 | &#160; int Get(int x, int y) {
      |  ^
a.cc:90:2: error: stray '#' in program
   90 | &#160; &#160; return cards[Encode(x, y)];
      |  ^
a.cc:90:9: error: stray '#' in program
   90 | &#160; &#160; return cards[Encode(x, y)];
      |         ^
a.cc:91:2: error: stray '#' in program
   91 | &#160; }
      |  ^
a.cc:92:2: error: stray '#' in program
   92 | &#160; void Set(int x, int y, int v) {
      |  ^
a.cc:93:2: error: stray '#' in program
   93 | &#160; &#160; cards[Encode(x, y)] = v;
      |  ^
a.cc:93:9: error: stray '#' in program
   93 | &#160; &#160; cards[Encode(x, y)] = v;
      |         ^
a.cc:94:2: error: stray '#' in program
   94 | &#160; }
      |  ^
a.cc:95:2: error: stray '#' in program
   95 | &#160; void Swap(int x1, int y1, int x2, int y2) {
      |  ^
a.cc:96:2: error: stray '#' in program
   96 | &#160; &#160; swap(cards[Encode(x1, y1)], cards[Encode(x2, y2)]);
      |  ^
a.cc:96:9: error: stray '#' in program
   96 | &#160; &#160; swap(cards[Encode(x1, y1)], cards[Encode(x2, y2)]);
      |         ^
a.cc:97:2: error: stray '#' in program
   97 | &#160; }
      |  ^
a.cc:98:2: error: stray '#' in program
   98 | &#160; void Holl(int &rx, int &ry) {
      |  ^
a.cc:99:2: error: stray '#' in program
   99 | &#160; &#160; REP(i, N) {
      |  ^
a.cc:99:9: error: stray '#' in program
   99 | &#160; &#160; REP(i, N) {
      |         ^
a.cc:100:2: error: stray '#' in program
  100 | &#160; &#160; &#160; if (cards[i] == 1) {
      |  ^
a.cc:100:9: error: stray '#' in program
  100 | &#160; &#160; &#160; if (cards[i] == 1) {
      |         ^
a.cc:100:16: error: stray '#' in program
  100 | &#160; &#160; &#160; if (cards[i] == 1) {
      |                ^
a.cc:101:2: error: stray '#' in program
  101 | &#160; &#160; &#160; &#160; rx = posX[i];
      |  ^
a.cc:101:9: error: stray '#' in program
  101 | &#160; &#160; &#160; &#160; rx = posX[i];
      |         ^
a.cc:101:16: error: stray '#' in program
  101 | &#160; &#160; &#160; &#160; rx = posX[i];
      |                ^
a.cc:101:23: error: stray '#' in program
  101 | &#160; &#160; &#160; &#160; rx = posX[i];
      |                       ^
a.cc:102:2: error: stray '#' in program
  102 | &#160; &#160; &#160; &#160; ry = posY[i];
      |  ^
a.cc:102:9: error: stray '#' in program
  102 | &#160; &#160; &#160; &#160; ry = posY[i];
      |         ^
a.cc:102:16: error: stray '#' in program
  102 | &#160; &#160; &#160; &#160; ry = posY[i];
      |                ^
a.cc:102:23: error: stray '#' in program
  102 | &#160; &#160; &#160; &#160; ry = posY[i];
      |                       ^
a.cc:103:2: error: stray '#' in program
  103 | &#160; &#160; &#160; &#160; return;
      |  ^
a.cc:103:9: error: stray '#' in program
  103 | &#160; &#160; &#160; &#160; return;
      |         ^
a.cc:103:16: error: stray '#' in program
  103 | &#160; &#160; &#160; &#160; return;
      |                ^
a.cc:103:23: error: stray '#' in program
  103 | &#160; &#160; &#160; &#160; return;
      |                       ^
a.cc:104:2: error: stray '#' in program
  104 | &#160; &#160; &#160; }
      |  ^
a.cc:104:9: error: stray '#' in program
  104 | &#160; &#160; &#160; }
      |         ^
a.cc:104:16: error: stray '#' in program
  104 | &#160; &#160; &#160; }
      |                ^
a.cc:105:2: error: stray '#' in program
  105 | &#160; &#160; }
      |  ^
a.cc:105:9: error: stray '#' in program
  105 | &#160; &#160; }
      |         ^
a.cc:106:2: error: stray '#' in program
  106 | &#160; &#160; assert(false);
      |  ^
a.cc:106:9: error: stray '#' in program
  106 | &#160; &#160; assert(false);
      |         ^
a.cc:107:2: error: stray '#' in program
  107 | &#160; }
      |  ^
a.cc:108:2: error: stray '#' in program
  108 | &#160; int HollX() {
      |  ^
a.cc:109:2: error: stray '#' in program
  109 | &#160; &#160; int x, y;
      |  ^
a.cc:109:9: error: stray '#' in program
  109 | &#160; &#160; int x, y;
      |         ^
a.cc:110:2: error: stray '#' in program
  110 | &#160; &#160; Holl(x, y);
      |  ^
a.cc:110:9: error: stray '#' in program
  110 | &#160; &#160; Holl(x, y);
      |         ^
a.cc:111:2: error: stray '#' in program
  111 | &#160; &#160; return x;
      |  ^
a.cc:111:9: error: stray '#' in program
  111 | &#160; &#160; return x;
      |         ^
a.cc:112:2: error: stray '#' in program
  112 | &#160; }
      |  ^
a.cc:113:2: error: stray '#' in program
  113 | &#160; int HollY() {
      |  ^
a.cc:114:2: error: stray '#' in program
  114 | &#160; &#160; int x, y;
      |  ^
a.cc:114:9: error: stray '#' in program
  114 | &#160; &#160; int x, y;
      |         ^
a.cc:115:2: error: stray '#' in program
  115 | &#160; &#160; Holl(x, y);
      |  ^
a.cc:115:9: error: stray '#' in program
  115 | &#160; &#160; Holl(x, y);
      |         ^
a.cc:116:2: error: stray '#' in program
  116 | &#160; &#160; return y;
      |  ^
a.cc:116:9: error: stray '#' in program
  116 | &#160; &#160; return y;
      |         ^
a.cc:117:2: error: stray '#' in program
  117 | &#160; }
      |  ^
a.cc:118:2: error: stray '#' in program
  118 | &#160; void CalcA() {
      |  ^
a.cc:119:2: error: stray '#' in program
  119 | &#160; &#160; int rev[16];
      |  ^
a.cc:119:9: error: stray '#' in program
  119 | &#160; &#160; int rev[16];
      |         ^
a.cc:120:2: error: stray '#' in program
  120 | &#160; &#160; REP(i, N) {
      |  ^
a.cc:120:9: error: stray '#' in program
  120 | &#160; &#160; REP(i, N) {
      |         ^
a.cc:121:2: error: stray '#' in program
  121 | &#160; &#160; &#160; rev[(int)cards[i] - 1] = i;
      |  ^
a.cc:121:9: error: stray '#' in program
  121 | &#160; &#160; &#160; rev[(int)cards[i] - 1] = i;
      |         ^
a.cc:121:16: error: stray '#' in program
  121 | &#160; &#160; &#160; rev[(int)cards[i] - 1] = i;
      |                ^
a.cc:122:2: error: stray '#' in program
  122 | &#160; &#160; }
      |  ^
a.cc:122:9: error: stray '#' in program
  122 | &#160; &#160; }
      |         ^
a.cc:127:2: error: stray '#' in program
  127 | &#160; &#160; a = 0;
      |  ^
a.cc:127:9: error: stray '#' in program
  127 | &#160; &#160; a = 0;
      |         ^
a.cc:128:2: error: stray '#' in program
  128 | &#160; &#160; FOR(i, 1, N) {
      |  ^
a.cc:128:9: error: stray '#' in program
  128 | &#160; &#160; FOR(i, 1, N) {
      |         ^
a.cc:129:2: error: stray '#' in program
  129 | &#160; &#160; &#160; a += dist[rev[i]][i];
      |  ^
a.cc:129:9: error: stray '#' in program
  129 | &#160; &#160; &#160; a += dist[rev[i]][i];
      |         ^
a.cc:129:16: error: stray '#' in program
  129 | &#160; &#160; &#160; a += dist[rev[i]][i];
      |                ^
a.cc:130:2: error: stray '#' in program
  130 | &#160; &#160; }
      |  ^
a.cc:130:9: error: stray '#' in program
  130 | &#160; &#160; }
      |         ^
a.cc:131:2: error: stray '#' in program
  131 | &#160; &#160; FOR(i, 3, N) {
      |  ^
a.cc:131:9: error: stray '#' in program
  131 | &#160; &#160; FOR(i, 3, N) {
      |         ^
a.cc:132:2: error: stray '#' in program
  132 | &#160; &#160; &#160; if (cards[i] == i + 1) { continue; }
      |  ^
a.cc:132:9: error: stray '#' in program
  132 | &#160; &#160; &#160; if (cards[i] == i + 1) { continue; }
      |         ^
a.cc:132:16: error: stray '#' in program
  132 | &#160; &#160; &#160; if (cards[i] == i + 1) { continue; }
      |                ^
a.cc:133:2: error: stray '#' in program
  133 | &#160; &#160; &#160; int fx = posX[i];
      |  ^
a.cc:133:9: error: stray '#' in program
  133 | &#160; &#160; &#160; int fx = posX[i];
      |         ^
a.cc:133:16: error: stray '#' in program
  133 | &#160; &#160; &#160; int fx = posX[i];
      |                ^
a.cc:134:2: error: stray '#' in program
  134 | &#160; &#160; &#160; int fy = posY[i];
      |  ^
a.cc:134:9: error: stray '#' in program
  134 | &#160; &#160; &#160; int fy = posY[i];
      |         ^
a.cc:134:16: error: stray '#' in program
  134 | &#160; &#160; &#160; int fy = posY[i];
      |                ^
a.cc:135:2: error: stray '#' in program
  135 | &#160; &#160; &#160; REP(dir, 4) {
      |  ^
a.cc:135:9: error: stray '#' in program
  135 | &#160; &#160; &#160; REP(dir, 4) {
      |         ^
a.cc:135:16: error: stray '#' in program
  135 | &#160; &#160; &#160; REP(dir, 4) {
      |                ^
a.cc:136:2: error: stray '#' in program
  136 | &#160; &#160; &