//https://www.geeksforgeeks.org/find-minimum-numbers-moves-needed-move-one-cell-matrix-another/
#include <bits/stdc++.h>
using namespace std;
#define N 4
class graph {
int v;
list<int> *adj;
public:
graph (int v) {
this->v= v;
adj= new list<int> [v];
};
void addEdge (int u, int w) {
adj[u].push_back(w);
adj[w].push_back(u);
}
void bfs(int , int d);
};
void graph::bfs (int s, int d) {
queue<int> q;
int level[v];
for (int i=0;i<v;i++)
level[i]= -1;
q.push(s);
level[s]=0;
while (!q.empty()) {
s= q.front();
q.pop();
list<int> ::iterator i;
for (i= adj[s].begin();i!= adj[s].end(); ++i ) {
if (level[*i]<0 || level[*i]>level[s]+1) {
level[*i]= level[s]+1;
q.push(*i);
}
}
}
cout<<level[d];
}
bool isSafe (int i, int j, int m[][N]) {
if (i<0 || i>N-1 || j<0 || j>=N || m[i][j]==0)
return false;
return true;
}
int minPath (int m[][N]) {
int s,d,k=0;
int v= N*N;
graph g(v);
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (m[i][j]!= 0) {
if (isSafe (i, j+1, m))
g.addEdge(k,k+1);
if (isSafe (i, j-1, m))
g.addEdge(k-1,k);
if (j<N-1 && isSafe (i+1,j,m))
g.addEdge(k,k+N);
if (i>0 && isSafe (i-1,j,m))
g.addEdge(k,k-N);
}
if (m[i][j]== 1)
s=k;
if (m[i][j]== 2)
d=k;
k++;
}
}
g.bfs(s,d);
}
int main() {
int M[N][N] = {{ 3 , 3 , 1 , 0 },
{ 3 , 0 , 3 , 3 },
{ 2 , 3 , 0 , 3 },
{ 0 , 3 , 3 , 3 }
};
minPath(M);
}