Shortest path in a Binary Maze - GeeksforGeeks
Given a MxN matrix where each element can either be 0 or 1. We need to find the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.
Expected time complexity is O(MN).
Read full article from Shortest path in a Binary Maze - GeeksforGeeks
Given a MxN matrix where each element can either be 0 or 1. We need to find the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.
Expected time complexity is O(MN).
The idea is inspired from Lee algorithm and uses BFS.
- We start from the source cell and calls BFS procedure.
- We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
- We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
- We LOOP till queue is not empty
- Dequeue front cell from the queue
- Return if the destination coordinates have reached.
- For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.
struct
Point
{
int
x;
int
y;
};
// An Data Structure for queue used in BFS
struct
queueNode
{
Point pt;
// The cordinates of a cell
int
dist;
// cell's distance of from the source
};
// check whether given cell (row, col) is a valid
// cell or not.
bool
isValid(
int
row,
int
col)
{
// return true if row number and column number
// is in range
return
(row >= 0) && (row < ROW) &&
(col >= 0) && (col < COL);
}
// These arrays are used to get row and column
// numbers of 4 neighbours of a given cell
int
rowNum[] = {-1, 0, 0, 1};
int
colNum[] = {0, -1, 1, 0};
// function to find the shortest path between
// a given source cell to a destination cell.
int
BFS(
int
mat[][COL], Point src, Point dest)
{
// check source and destination cell
// of the matrix have value 1
if
(!mat[src.x][src.y] || !mat[dest.x][dest.y])
return
INT_MAX;
bool
visited[ROW][COL];
memset
(visited,
false
,
sizeof
visited);
// Mark the source cell as visited
visited[src.x][src.y] =
true
;
// Create a queue for BFS
queue<queueNode> q;
// distance of source cell is 0
queueNode s = {src, 0};
q.push(s);
// Enqueue source cell
// Do a BFS starting from source cell
while
(!q.empty())
{
queueNode curr = q.front();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if
(pt.x == dest.x && pt.y == dest.y)
return
curr.dist;
// Otherwise dequeue the front cell in the queue
// and enqueue its adjacent cells
q.pop();
for
(
int
i = 0; i < 4; i++)
{
int
row = pt.x + rowNum[i];
int
col = pt.y + colNum[i];
// if adjacent cell is valid, has path and
// not visited yet, enqueue it.
if
(isValid(row, col) && mat[row][col] &&
!visited[row][col])
{
// mark cell as visited and enqueue it
visited[row][col] =
true
;
queueNode Adjcell = { {row, col},
curr.dist + 1 };
q.push(Adjcell);
}
}
}
//return -1 if destination cannot be reached
return
INT_MAX;
}