Shortest Path in Binary Matrix: A Simple Algorithmic Approach

Introduction

Graphs are an essential data structure in computer science, and they are used in various applications. One of the common problems that arise when working with graphs is finding the shortest path in a binary matrix. In this blog, we will discuss a simple algorithmic approach to solve this problem.

Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix from the top-left corner (0, 0) to the bottom-right corner (n - 1, n - 1). If there is no such path, return -1.

Background Theory

Before we dive into the algorithmic approach, let's first understand some basic concepts of graphs. A graph is a data structure that consists of a set of vertices and a set of edges. Each edge connects two vertices, and it represents a relationship between them. A graph can be represented using an adjacency matrix or an adjacency list.

Algorithmic Approach

The algorithmic approach to finding the shortest path in a binary matrix involves the following steps:

Initialize a queue to perform a breadth-first search.
Initialize a 2D array to keep track of visited vertices.
Initialize a counter to keep track of the length of the path.
Add the starting vertex to the queue.
While the queue is not empty, perform a breadth-first search to visit all connected vertices.
Mark all visited vertices as true.
Return the length of the path.

Here is the implementation of the algorithm in C++:

int shortestPathBinaryMatrix(vector<vector<int>> &grid)
{
    int n = grid.size();
    if (n == 1 && grid[0][0] == 0)
        return 1;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
        return -1;
    queue<pair<pair<int, int>, int>> q;
    q.push({{0, 0}, 1});
    int dir[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
    while (!q.empty())
    {
        int len = q.size();
        while (len--)
        {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int z = q.front().second;
            q.pop();

            for (int i = 0; i < 8; i++)
            {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n)
                {
                    if (nx == n - 1 && ny == n - 1)
                        return z + 1;
                    if (grid[nx][ny] == 0)
                    {
                        grid[nx][ny] = 1;
                        q.push({{nx, ny}, z + 1});
                    }
                }
            }
        }
    }
    return -1;
}

Time Complexity

The time complexity of this algorithm is O(n^2), where n is the size of the binary matrix.

Space Complexity

The space complexity of this algorithm is O(n^2), as we are using a 2D array to keep track of visited vertices and a queue to perform a breadth-first search.

Conclusion

In conclusion, we have discussed a simple algorithmic approach to finding the shortest path in a binary matrix. This approach has a time complexity of O(n^2) and a space complexity of O(n^2). This algorithm is efficient and can be used in various applications that involve graphs.

Stackable