Shortest Path in a Binary Matrix

In a MxN matrix , a cell can either be 0 or 1. Find the shortest path between a given source cell to a destination cell under the following condition.

Traverse can happen through a cell if its value is 1
Move can be made in left, right, top and bottom directions only

Input:
int matrix[ROW][COL] = {
{1, 0, 1, 1, 1, 1, 0, 1, 1, 0},
{1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 0, 1},
{1, 1, 1, 0, 1, 1, 1, 1, 1, 0},
{1, 0, 1, 0, 1, 1, 0, 1, 1, 0},
{1, 0, 0, 0, 1, 0, 1, 0, 1, 1},
{1, 0, 1, 1, 1, 1, 0, 1, 1, 1},
{1, 1, 0, 1, 1, 0, 1, 0, 0, 1}};
Source = {0, 0};
Destination = {8, 9};
Output:
Shortest Path is 21

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define ROW 9
#define COL 10

int matrix[ROW][COL] = {
    {1, 0, 1, 1, 1, 1, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 1, 0, 1, 1},
    {1, 1, 1, 0, 0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 1, 0, 1},
    {1, 1, 1, 0, 1, 1, 1, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 0, 1, 1, 0},
    {1, 0, 0, 0, 1, 0, 1, 0, 1, 1}, {1, 0, 1, 1, 1, 1, 0, 1, 1, 1},
    {1, 1, 0, 1, 1, 0, 1, 0, 0, 1}};

typedef struct Node {
  int row;
  int col;
  int dist;
  Node(int r, int c, int d) {
    row = r;
    col = c;
    dist = d;
  }
} Node;

int row_num[4] = {-1, 0, 0, 1};
int col_name[4] = {0, -1, 1, 0};

bool isValid(int row, int col) {
  if (row >= 0 && row < ROW && col >= 0 && col < COL) return true;
  return false;
}
int bfs(int srow, int scol, int drow, int dcol) {
  bool visited[ROW][COL] = {0};
  queue<Node> q;
  Node src(srow, scol, 0);
  q.push(src);
  visited[srow][scol] = true;
  vector<Node> path;
  while (!q.empty()) {
    Node u = q.front();
    q.pop();
    path.push_back(u);
    int u_row = u.row;
    int u_col = u.col;

    if (u_row == drow && u_col == dcol) return u.dist;
    for (int i = 0; i < 4; i++) {
      int v_row = u.row + row_num[i];
      int v_col = u.col + col_name[i];
      if (isValid(v_row, v_col) && !visited[v_row][v_col] && matrix[v_row][v_col]) {
        q.push(Node(v_row, v_col, u.dist + 1));
        visited[v_row][v_col] = true;
      }
    }
  }
  return -1;
}

int main() {
  cout << bfs(0, 0, 8, 9) << endl;
  return 0;
}

References

Related Posts