C++ :

#include<bits/stdc++.h>
using namespace std;
int n,w,t,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
map<int,int>ans;
queue<int>q;
int main(){
	cin>>n;
	ans[n]=0;
	q.push(n);
	while(!q.empty()){
		w=q.front();q.pop();
		t=w;
		if(t==255) cout<<ans[t];
		int a[4][4],sum=15;
		while(sum>=0){
			a[sum/4][sum%4]=t%2;
			t/=2,sum--;
		}
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				for(int k=0;k<4;k++){
					int tx=i+dx[k],ty=j+dy[k],len=0;
					if(tx<0||ty<0||tx>=4||ty>=4) continue;
					if(a[i][j]==a[tx][ty])	continue;
					swap(a[i][j],a[tx][ty]);
					for(int h=0;h<4;h++){
						for(int l=0;l<4;l++) len=len*2+a[h][l];}
					if(ans.count(len)==false){
						ans[len]=ans[w]+1;
						q.push(len);
					}
					swap(a[i][j],a[tx][ty]);
				}
			}
		}
	}
	return 0;
}