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<char> 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:86:30: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<char>'
   86 |                 int val=calc(v);
      |                              ^
a.cc:55:22: note: in passing argument 1 of 'int calc(std::vector<int>&)'
   55 | int calc(vector<int>&v){
      |          ~~~~~~~~~~~~^
a.cc:93:55: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<char>'
   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));
      |                                                       ^
a.cc:55:22: note: in passing argument 1 of 'int calc(std::vector<int>&)'
   55 | int calc(vector<int>&v){
      |          ~~~~~~~~~~~~^
a.cc:99:55: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<char>'
   99 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor+1,depth+1),q.push(make_pair(v,f));
      |                                                       ^
a.cc:55:22: note: in passing argument 1 of 'int calc(std::vector<int>&)'
   55 | int calc(vector<int>&v){
      |          ~~~~~~~~~~~~^
a.cc:105:55: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<char>'
  105 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor-X,depth+1),q.push(make_pair(v,f));
      |                                                       ^
a.cc:55:22: note: in passing argument 1 of 'int calc(std::vector<int>&)'
   55 | int calc(vector<int>&v){
      |          ~~~~~~~~~~~~^
a.cc:111:55: error: invalid initialization of reference of type 'std::vector<int>&' from expression of type 'std::vector<char>'
  111 |                         if(m.find(v)==m.end() && calc(v)<=val+THRESHOLD)m[v]=make_pair(coor+X,depth+1),q.push(make_pair(v,f));
      |                                                       ^
a.cc:55:22: note: in passing argument 1 of 'int calc(std::vector<int>&)'
   55 | int calc(vector<int>&v){
      |          ~~~~~~~~~~~~^