#include <bits/stdc++.h>
using namespace std;
#define HORI 3
#define VERT 3
struct Point
{
int a;
int b;
};
struct queueNode
{
Point de;
int sam;
};
bool isValid(int hori, int vert)
{
return (hori >= 0) && (hori < HORI) &&
(vert >= 0) && (vert < VERT);
}
int horiNum[] = {9, 7, 9, 2};
int vertNum[] = {3, 3, 4, 5};
int BFS(int lk[][VERT], Point ace, Point hello)
{
if (!lk[ace.a][ace.b] || !lk[hello.a][hello.b])
return -1;
bool visited[HORI][VERT];
memset(visited, false, sizeof visited);
visited[ace.a][ace.b] = true;
queue<queueNode> e;
queueNode s = {ace, 0};
e.push(s);
while (!e.empty())
{
queueNode curr = e.front();
Point de = curr.de;
if (de.a == hello.a && de.b == hello.b)
return curr.sam;
e.pop();
for (int i = 0; i < 4; i++)
{
int hori = de.a + horiNum[i];
int vert = de.b + vertNum[i];
if (isValid(hori, vert) && lk[hori][vert] &&
!visited[hori][vert])
{
visited[hori][vert] = true;
queueNode Adjcell = { {hori, vert},
curr.sam + 1 };
e.push(Adjcell);
}
}
}
return -1;
}
int main()
{
int lk[HORI][VERT] =
{
{ 3, 9, 2 },
{ 4, 5, 3 },
{ 0, 3, 0 }
};
Point source = {0, 0};
Point hello = {1, 1};
int sam = BFS(lk, source, hello);
if (sam != 1)
cout << "Shortest Path:" << sam ;
else
cout << "Failed!!!";
return 0;
}
