#include <iostream>
            #include <queue>
            #include <vector>
            #include <map>
            #include <time.h>
            
            int cnt = 0;
            int puz_state[1000000][16];
            int p_state[1000000];
            
            
            struct state { int puzzle[16]; int depth; int f_n; int id;
                bool operator>(const state &s) const {
                    return f_n > s.f_n;
                }
            };
            
            state start = { {5, 3, 4, 13, 2, 0, 1, 6, 10, 11, 8, 7, 9, 12, 15, 14}, 0, 0, 0};
            state goal = { {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}, 0, 0, 0};    // evaluation
            std::priority_queue <state, std::vector<state>, std::greater<state> > open;
            std::vector<state> closed;
            
            bool IsFinished(state s){
                for (int i = 0; i < 15; i++) {
                   if (s.puzzle[i] != goal.puzzle[i]) return false;
                }
                return true;
            }
            
            int ManhattanOne(int n, int place){
                if (goal.puzzle[n] == 0) return 0;
                int q, r;
                q = abs(place / 4 - n / 4);
                r = abs(place % 4 - n % 4);
                return q + r;
            }
            
            int manhattan(state s){
                int eval = 0;
                std::map<int, int> goalplace;
                for (int i = 0; i < 16; i++) goalplace[goal.puzzle[i]] = i;
                for (int i = 0; i < 16; i++) eval += ManhattanOne(goalplace[s.puzzle[i]], i);
                return eval;
            }
            
            bool IsSamePuzzle(state s1, state s2){
                for (int i = 0; i < 16; i++) {
                    if (s1.puzzle[i] != s2.puzzle[i]) return false;
                }
                return true;
            }
            
            bool InClosed(state s){
                for (int i = 0; i < closed.size(); i++) {
                    if (IsSamePuzzle(s, closed[i])) return true;
                }
                return false;
            }
            
            void print_ans(int n){
                if(n != 0) print_ans(p_state[n]);
                for(int i = 0; i < 4; i++){
                    for(int j = 0; j < 4; j++){
                        printf("%d ", puz_state[n][i*4 + j] );
                    }
                    printf("\n");
                }
                printf("\n");
            }
            
            void AStar(){
                state now = open.top();
                open.pop();
                closed.push_back(now);
                if (IsFinished(now)){
                    print_ans(now.id);
                    printf("\ndepth = %d\n", now.depth);
                    return;
                }
                state s = now;    
                int zero;
                for (int i = 0; i < 16; i++) {
                    if (now.puzzle[i] == 0) zero = i;
                }
                if (zero - 4 >= 0) {
                    std::swap(s.puzzle[zero - 4], s.puzzle[zero]);
                    if (!InClosed(s)) {
                        cnt++; s.id = cnt;
                        p_state[cnt] = now.id;
                        for(int i = 0; i < 16; i++) puz_state[cnt][i] = s.puzzle[i];
                        s.depth++;
                        s.f_n = manhattan(s) + s.depth;
                        open.push(s);
                    }
                    s = now;
                }
                if (zero % 4 != 0) {
                    std::swap(s.puzzle[zero - 1], s.puzzle[zero]);
                    if (!InClosed(s)) {
                        cnt++; s.id = cnt;
                        p_state[cnt] = now.id;
                        for(int i = 0; i < 16; i++) puz_state[cnt][i] = s.puzzle[i];
                        s.depth++;
                        s.f_n = manhattan(s) + s.depth;
                        open.push(s);
                    }
                    s = now;
                }
                if (zero % 4 != 3) {
                    std::swap(s.puzzle[zero + 1], s.puzzle[zero]);
                    if (!InClosed(s)) {
                        cnt++; s.id = cnt;
                        p_state[cnt] = now.id;
                        for(int i = 0; i < 16; i++) puz_state[cnt][i] = s.puzzle[i];
                        s.depth++;
                        s.f_n = manhattan(s) + s.depth;
                        open.push(s);
                    }
                    s = now;
                }
                if (zero + 4 < 16) {
                    std::swap(s.puzzle[zero + 4], s.puzzle[zero]);
                    if (!InClosed(s)) {
                        cnt++; s.id = cnt;
                        p_state[cnt] = now.id;
                        for(int i = 0; i < 16; i++) puz_state[cnt][i] = s.puzzle[i];
                        s.depth++;
                        s.f_n = manhattan(s) + s.depth;
                        open.push(s);
                    }
                }
                AStar();
                return;
            }
            
            
            int main(){
                clock_t s = clock();
                start.f_n = manhattan(start);
                open.push(start);
                for(int i = 0; i < 16; i++) puz_state[0][i] = start.puzzle[i];
                AStar();
                clock_t e = clock();
                std::cout << (double)(e-s)/CLOCKS_PER_SEC << std::endl;
            
                return 0;
            }