blahblahpyatnashki

#include <iostream>
#include <cstdio>
#include <array>
#include <set>
#include <algorithm>
#include <vector>
#include <map>


using namespace std;

typedef array<int, 16> board;
typedef unsigned long long desc;

void printboard(const board& b) {
    for (int row = 0; row < 4; ++row) {
        for (int col = 0; col < 4; ++col) {
            printf("%3d", b[row*4+col]);
        }
        printf("\n");
    }
}

int coord2ind(pair<int, int> c) {
    return c.first * 4 + c.second;
}

pair<int,int> ind2coord(int i) {
    return make_pair(i / 4, i % 4);
}

desc b2desc(const board& b) {
    desc h = 0;
    for (int v : b) {
        h *= 16;
        h += v;
    }
    return h;
}

board desc2b(desc h) {
    board b = {};
    for (int i = 15; i >= 0; --i) {
        b[i] = h % 16;
        h /= 16;
    }
    return b;
}

int heuristic(const board& b) {
    int dist = 0;
    for (int i = 0; i < 16; ++i) {
        int v = b[i];
        if (v == 0) continue;
        auto curr_c = ind2coord(i);
        auto dest_c = ind2coord(v-1);
        dist += abs(curr_c.first - dest_c.first);
        dist += abs(curr_c.second - dest_c.second);
    }
    return dist;
}

int find_hole(const board& b) {
    for (int i = 0; i < 16; ++i) {
        if (b[i] == 0) return i;
    }
    return -1;
}

board finish() {
    return board{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
}

int oddness(const board& b) {
    vector<int> z;
    for (int i = 0; i < 16; ++i) {
        if (b[i] != 0) z.push_back(b[i]-1);
    }
    set<int> done;
    int result = 0;
    for (int st = 0; st < 15; ++st) {
        if (done.count(st)) continue;
        int i = st;
        int cnt = 0;
        do {
            done.insert(i);
            i = z[i];
            cnt++;
        } while (i != st);
        result += cnt-1;
    }
    return result % 2;
}

void unroll_solution(const map<desc, desc>& visited, desc last, desc first) {

}

void go(const board& start_b) {
    map<desc, desc> visited;
    set<tuple<int, int, desc>> q; // total, before, desc

    desc start_d = b2desc(start_b);
    q.insert(make_tuple(heuristic(start_b), 0, start_d));
    visited[start_d] = 0;
    desc finishdesc = b2desc(finish());

    while (!q.empty()) {
        int _, before;
        desc d;
        tie(_, before, d) = *q.begin();
        q.erase(q.begin());
        board b = desc2b(d);

//        printf("Visiting:\n");
//        printboard(b);
        static int c = 0;
        ++c;
        if (c == 10000000) {
            printf("Limit reached");
            return;
        }

        if (d == finishdesc) {
            printf("FOUND!!! In %d moves\n", before);
            return;
        }

        pair<int,int> moves[4];
        int nmoves = 0;

        int hole_i = find_hole(b);
        auto hole_c = ind2coord(hole_i);
        if (hole_c.first > 0) {
            moves[nmoves++] = make_pair(hole_c.first - 1, hole_c.second);
        }
        if (hole_c.second > 0) {
            moves[nmoves++] = make_pair(hole_c.first, hole_c.second - 1);
        }
        if (hole_c.first < 3) {
            moves[nmoves++] = make_pair(hole_c.first + 1, hole_c.second);
        }
        if (hole_c.second < 3) {
            moves[nmoves++] = make_pair(hole_c.first, hole_c.second + 1);
        }
        for (int imove = 0; imove < nmoves; imove++) {
            auto move = moves[imove];
            int move_i = coord2ind(move);
            board b2 = b;
            swap(b2[move_i], b2[hole_i]);
            desc d2 = b2desc(b2);
            if (visited.count(d2)) {
                continue;
            }
            visited[d2] = d;
            q.insert(make_tuple(before + 1 + heuristic(b2), before + 1, d2));
        }
    }
    printf ("Q is empty, eh?\n");
}

int main(int argc, const char * argv[]) {
//    board b = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15};
    board b = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9, 12, 11, 13 ,14 ,15, 0};
//    board b3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};

    if (oddness(b) == 1) {
        printf("It's odd.");
        return 0;
    }

    go(b);

    return 0;
}