Language: C++

#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;
struct Puzzle{
        int a[4][4];
        int calcDist(){
                int u,v, sum=0;
                for(int i=1;i<16;i++){
                        for(int j=0;j<16;j++){
                                if(i==a[j/4][j%4]){
                                        u = j/4;
                                        v = j%4;
                                        break;
                                }
                        }
                        sum += abs((i-1)/4-u) + abs((i-1)%4-v);

                }
                return sum;
        }
};

bool operator< (const Puzzle &s, const Puzzle &t){
        for(int i=0;i<16;i++){
                if(s.a[i/4][i%4]==t.a[i/4][i%4]) continue;
                return s.a[i/4][i%4] < t.a[i/4][i%4];
        }
        return false;
}

struct Status{
        Puzzle p;
        int c,i,j;
        int distFromTarget;
        Status(Puzzle p1, int cnt){
                p = p1;
                for(int k=0;k<16;k++) {
                        if(p.a[k/4][k%4]==0){
                                i=k/4;
                                j=k%4;
                        }
                }
                distFromTarget = p.calcDist();
                c = cnt;
        }
};

int solve(Puzzle p0){
        set<Puzzle> visited;
        priority_queue<Status> que;
        Status s0(p0,0);
        que.push(s0);
        while(!que.empty()){
                Status s = que.top();que.pop();
                Puzzle p = s.p;
                if(visited.find(p)!=visited.end()) continue;
                if(s.distFromTarget==0) return s.c;
                visited.insert(p);

                Puzzle tmp;
                if(s.i!=0) {
                        tmp = p;
                        swap(tmp.a[s.i][s.j], tmp.a[s.i-1][s.j]);
                        if(visited.find(tmp)==visited.end()) que.push(Status(tmp, s.c+1));
                }
                if(s.j!=0) {
                        tmp = p;
                        swap(tmp.a[s.i][s.j], tmp.a[s.i][s.j-1]);
                        if(visited.find(tmp)==visited.end()) que.push(Status(tmp, s.c+1));
                }
                if(s.i!=3) {
                        tmp = p;
                        swap(tmp.a[s.i][s.j], tmp.a[s.i+1][s.j]);
                        if(visited.find(tmp)==visited.end()) que.push(Status(tmp, s.c+1));
                }
                if(s.j!=3) {
                        tmp = p;
                        swap(tmp.a[s.i][s.j], tmp.a[s.i][s.j+1]);
                        if(visited.find(tmp)==visited.end()) que.push(Status(tmp, s.c+1));
                }
        }
        return -1;
}

int main(){
        Puzzle p;
        for(int i=0;i<16;i++) {
                cin>>p.a[i/4][i%4];
        }

        cout<<solve(p)<<endl;
}




Compiler output:
In file included from /usr/include/c++/14/string:49,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_function.h: In instantiation of 'constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Status]':
/usr/include/c++/14/bits/predefined_ops.h:196:23:   required from 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<Status*, std::vector<Status, std::allocator<Status> > >; _Value = Status; _Compare = std::less<Status>]'
  196 |         { return bool(_M_comp(*__it, __val)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Status*, vector<Status, allocator<Status> > >; _Distance = long int; _Tp = Status; _Compare = __gnu_cxx::__ops::_Iter_comp_val<less<Status> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:216:23:   required from 'void std::push_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Status*, vector<Status, allocator<Status> > >; _Compare = less<Status>]'
  216 |       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  217 |                        _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_queue.h:739:16:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = Status; _Sequence = std::vector<Status, std::allocator<Status> >; _Compare = std::less<Status>; value_type = Status]'
  739 |         std::push_heap(c.begin(), c.end(), comp);
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:54:17:   required from here
   54 |         que.push(s0);
      |         ~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_function.h:405:20: error: no match for 'operator<' (operand types are 'const Status' and 'const Status')
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
In file included from /usr/include/c++/14/string:48:
/usr/include/c++/14/bits/stl_iterator.h:448:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_Iterator>&)'
  448 |     operator<(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:448:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Status' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)'
  493 |     operator<(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:493:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Status' is not derived from 'const std::reverse_iterator<_Iterator>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)'
 1694 |     operator<(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1694:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Status' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator<(const move_iterator<_IteratorL>&, const move_iterator<_IteratorL>&)'
 1760 |     operator<(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/14/bits/stl_iterator.h:1760:5: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_function.h:405:20: note:   'const Status' is not derived from 'const std::move_iterator<_IteratorL>'
  405 |       { return __x < __y; }
      |                ~~~~^~~~~
a.cc:25:6: note: candidate: 'bool operator<(const Puzzle&, const Puzzle&)'
   25 | bool operator< (const Puzzle &s, const Puzzle &t){
      |      ^~~~~~~~
a.cc:25:31: note:   no known conversion for argument 1 from 'const Status' to 'const Puzzle&'
   25 | bool operator< (const Puzzle &s, const Puzzle &t){
      |                 ~~~~~~~~~~~~~~^