#include<bits/stdc++.h>
#define a Array
#define d distances
#define v visit
#define pii pair<int, int>
using namespace std;
int x[] = {1, -1, 0, 0};
int y[] = {0, 0, 1, -1};
int a[1000][1000], d[1000][1000], v[1000][1000];
int row, column;
bool check(int r, int c)
{
return (r >= 0) && (r < row) && (c >= 0) && (c < column);
}
int bfs(int start_x, int start_y, int finish_x, int finish_y)
{
int i, j;
v[start_x][start_y] = 1;
queue<pii>q;
q.push(pii(start_x, start_y));
while(!q.empty())
{
pii r = q.front();
q.pop();
if(r.first == finish_x && r.second == finish_y)
return d[finish_x][finish_y];
for(i=0;i<4;i++)
{
int tx = r.first + x[i];
int ty = r.second + y[i];
if(check(tx, ty) && a[tx][ty] == 1 && v[tx][ty] == 0)
{
v[tx][ty] = 1;
d[tx][ty] = d[r.first][r.second] + 1;
q.push(pii(tx, ty));
}
}
}
return -1;
}
int main()
{
cout << "Enter Row And Column :: ";
cin >> row >> column;
int i, j, start_x, start_y, finish_x, finish_y;
cout << "\nEnter Graph Input :: \n";
for(i=0;i<row;i++)
{
for(j=0;j<column;j++)
{
cin >> a[i][j];
}
}
cout << "\nEnter Point Start :: ";
cin >> start_x >> start_y;
cout << "\nEnter Point End :: ";
cin >> finish_x >> finish_y;
int total_distance = bfs(start_x, start_y, finish_x, finish_y);
if(total_distance != -1)
cout << "\nShortest Path is :: " << total_distance << "\n";
else
cout << "\nShortest Path Doesn't Exist.\n";
return 0;
}
#define a Array
#define d distances
#define v visit
#define pii pair<int, int>
using namespace std;
int x[] = {1, -1, 0, 0};
int y[] = {0, 0, 1, -1};
int a[1000][1000], d[1000][1000], v[1000][1000];
int row, column;
bool check(int r, int c)
{
return (r >= 0) && (r < row) && (c >= 0) && (c < column);
}
int bfs(int start_x, int start_y, int finish_x, int finish_y)
{
int i, j;
v[start_x][start_y] = 1;
queue<pii>q;
q.push(pii(start_x, start_y));
while(!q.empty())
{
pii r = q.front();
q.pop();
if(r.first == finish_x && r.second == finish_y)
return d[finish_x][finish_y];
for(i=0;i<4;i++)
{
int tx = r.first + x[i];
int ty = r.second + y[i];
if(check(tx, ty) && a[tx][ty] == 1 && v[tx][ty] == 0)
{
v[tx][ty] = 1;
d[tx][ty] = d[r.first][r.second] + 1;
q.push(pii(tx, ty));
}
}
}
return -1;
}
int main()
{
cout << "Enter Row And Column :: ";
cin >> row >> column;
int i, j, start_x, start_y, finish_x, finish_y;
cout << "\nEnter Graph Input :: \n";
for(i=0;i<row;i++)
{
for(j=0;j<column;j++)
{
cin >> a[i][j];
}
}
cout << "\nEnter Point Start :: ";
cin >> start_x >> start_y;
cout << "\nEnter Point End :: ";
cin >> finish_x >> finish_y;
int total_distance = bfs(start_x, start_y, finish_x, finish_y);
if(total_distance != -1)
cout << "\nShortest Path is :: " << total_distance << "\n";
else
cout << "\nShortest Path Doesn't Exist.\n";
return 0;
}
Comments
Post a Comment