Shortest path in a Binary Maze(By BFS)

#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;
}

Comments