Language: C++

#include <vector>
#include <queue>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define X 4
#define Y 4
#define THRESHOLD 2

namespace std{
	template<typename T>
	inline void hash_combine(size_t& seed, T const& v){
		seed ^= hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
	}
    template<typename It>
    inline size_t hash_range(It first, It last){
		size_t seed=0;
		hash_range(seed,first,last);
		return seed;
	}
	template<typename It>
	inline void hash_range(size_t& seed, It first, It last){
		for(;first!=last;++first)hash_combine(seed, *first);
	}
	template<typename A,typename B>
	class hash<pair<A,B>>{
		public:
		size_t operator()(pair<A,B> const &p) const{
			size_t seed=0;
			hash_combine(seed,p.first);
			hash_combine(seed,p.second);
			return seed;
		}
	};
	template<typename T,size_t N>
	class hash<array<T,N>>{
		public:
		size_t operator()(array<T,N> const &container) const{
			return hash_range(container.begin(),container.end());
		}
	};
	template<typename T,typename A>
	class hash<vector<T,A>>{
		public:
		size_t operator()(vector<T,A> const &container) const{
			return hash_range(container.begin(),container.end());
		}
	};
}

int manhattan(int x1,int y1,int x2,int y2){
	return abs(x1-x2)+abs(y1-y2);
}
int calc(vector<int>&v){
	int s=0;
	for(int coor=0;coor<X*Y;coor++){
		if(v[coor]!=0){
			s+=manhattan(coor%X,coor/X,(v[coor]-1)%X,(v[coor]-1)/X);
		}else{
			s+=manhattan(coor%X,coor/X,X-1,Y-1);
		}
	}
	return s;
}
int main(){
	int i=1,start_point;
	vector<char>start(X*Y),goal;
	for(;i<X*Y;i++)goal.push_back(i);goal.push_back(0);
	for(i=0;i<X*Y;i++){
		scanf("%d",&start[i]);
		if(start[i]==0)start_point=i;
	}
	if(start==goal){puts("0");return 0;}

	unordered_map<vector<char>,pair<char,char> >mstart,mgoal;
	queue<pair<vector<char>,bool> >q;
	mstart[start]=make_pair(start_point,0);
	mgoal[goal]=make_pair(X*Y-1,0);
	q.push(make_pair(start,false));
	q.push(make_pair(goal,true));
	for(;!q.empty();){
		vector<int> v=q.front().first;
		bool f=q.front().second;
		q.pop();
		int val=calc(v);
		unordered_map<vector<char>,pair<char,char> >&m=f?mgoal:mstart;
		unordered_map<vector<char>,pair<char,char> >&m2=f?mstart:mgoal;
		int coor=m[v].first,x=coor%X,y=coor/X;
		int depth=m[v].second;
		if(0<x){
			swap(v[coor],v[coor-1]);
			if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-1,depth+1),q.push(make_pair(v,f));
			if(m2.find(v)!=m2.end()){printf("%d\n",m2[v].second+depth+1);return 0;}
			swap(v[coor],v[coor-1]);
		}
		if(x<X-1){
			swap(v[coor],v[coor+1]);
			if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor+1,depth+1),q.push(make_pair(v,f));
			if(m2.find(v)!=m2.end()){printf("%d\n",m2[v].second+depth+1);return 0;}
			swap(v[coor],v[coor+1]);
		}
		if(0<y){
			swap(v[coor],v[coor-X]);
			if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-X,depth+1),q.push(make_pair(v,f));
			if(m2.find(v)!=m2.end()){printf("%d\n",m2[v].second+depth+1);return 0;}
			swap(v[coor],v[coor-X]);
		}
		if(y<Y-1){
			swap(v[coor],v[coor+X]);
			if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor+X,depth+1),q.push(make_pair(v,f));
			if(m2.find(v)!=m2.end()){printf("%d\n",m2[v].second+depth+1);return 0;}
			swap(v[coor],v[coor+X]);
		}
	}
}

Compiler output:
a.cc: In function 'int main()':
a.cc:83:41: error: conversion from 'vector<char>' to non-scalar type 'vector<int>' requested
   83 |                 vector<int> v=q.front().first;
      |                               ~~~~~~~~~~^~~~~
a.cc:89:27: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::vector<char>, std::pair<char, char> >' and 'std::vector<int>')
   89 |                 int coor=m[v].first,x=coor%X,y=coor/X;
      |                           ^
In file included from /usr/include/c++/14/unordered_map:41,
                 from a.cc:3:
/usr/include/c++/14/bits/unordered_map.h:987:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  987 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:987:34: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&' {aka 'const std::vector<char>&'}
  987 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/unordered_map.h:991:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  991 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:991:29: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&&' {aka 'std::vector<char>&&'}
  991 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
a.cc:90:28: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::vector<char>, std::pair<char, char> >' and 'std::vector<int>')
   90 |                 int depth=m[v].second;
      |                            ^
/usr/include/c++/14/bits/unordered_map.h:987:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  987 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:987:34: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&' {aka 'const std::vector<char>&'}
  987 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/unordered_map.h:991:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  991 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:991:29: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&&' {aka 'std::vector<char>&&'}
  991 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
a.cc:91:22: error: 'x' was not declared in this scope
   91 |                 if(0<x){
      |                      ^
a.cc:93:34: error: no matching function for call to 'std::unordered_map<std::vector<char>, std::pair<char, char> >::find(std::vector<int>&)'
   93 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-1,depth+1),q.push(make_pair(v,f));
      |                            ~~~~~~^~~
/usr/include/c++/14/bits/unordered_map.h:876:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::find(const key_type&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; iterator = std::__detail::_Insert_base<std::vector<char>, std::pair<const std::vector<char>, std::pair<char, char> >, std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >, std::__detail::_Select1st, std::equal_to<std::vector<char> >, std::hash<std::vector<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::iterator; key_type = std::vector<char>]'
  876 |       find(const key_type& __x)
      |       ^~~~
/usr/include/c++/14/bits/unordered_map.h:876:28: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&' {aka 'const std::vector<char>&'}
  876 |       find(const key_type& __x)
      |            ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/unordered_map.h:887:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::find(const key_type&) const [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; const_iterator = std::__detail::_Insert_base<std::vector<char>, std::pair<const std::vector<char>, std::pair<char, char> >, std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >, std::__detail::_Select1st, std::equal_to<std::vector<char> >, std::hash<std::vector<char> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, false, true> >::const_iterator; key_type = std::vector<char>]'
  887 |       find(const key_type& __x) const
      |       ^~~~
/usr/include/c++/14/bits/unordered_map.h:887:28: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&' {aka 'const std::vector<char>&'}
  887 |       find(const key_type& __x) const
      |            ~~~~~~~~~~~~~~~~^~~
a.cc:93:74: error: no match for 'operator[]' (operand types are 'std::unordered_map<std::vector<char>, std::pair<char, char> >' and 'std::vector<int>')
   93 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-1,depth+1),q.push(make_pair(v,f));
      |                                                                          ^
/usr/include/c++/14/bits/unordered_map.h:987:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  987 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:987:34: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&' {aka 'const std::vector<char>&'}
  987 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/14/bits/unordered_map.h:991:7: note: candidate: 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&&) [with _Key = std::vector<char>; _Tp = std::pair<char, char>; _Hash = std::hash<std::vector<char> >; _Pred = std::equal_to<std::vector<char> >; _Alloc = std::allocator<std::pair<const std::vector<char>, std::pair<char, char> > >; mapped_type = std::pair<char, char>; key_type = std::vector<char>]'
  991 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/14/bits/unordered_map.h:991:29: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::unordered_map<std::vector<char>, std::pair<char, char> >::key_type&&' {aka 'std::vector<char>&&'}
  991 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
a.cc:93:110: error: no matching function for call to 'std::queue<std::pair<std::vector<char>, bool> >::push(std::pair<std::vector<int>, bool>)'
   93 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-1,depth+1),q.push(make_pair(v,f));
      |                                                                                                        ~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/queue:66,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_queue.h:283:7: note: candidate: 'void std::queue<_Tp, _Sequence>::push(const value_type&) [with _Tp = std::pair<std::vector<char>, bool>; _Se