BFS and DFS are usually used in searching problem. But for a specific kind of problem, we should use a optimized BFS, Multi-end BFS to guarantee the efficiency of the solution.

This kind of problems has the following features:

  1. There are many entrances in the searching space.
  2. We want the minimum or the maximum solutions.
  3. The elements can affect each other.

Multi-end BFS is to set all the entrances as the root of BFS at the same time and push them to the queue. Then make use of the their connections to solve the problem.

Look at the following two examples.

Problem

LeetCode 286

Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

  1. -1 – A wall or an obstacle.
  2. 0 – A gate.
  3. INF – Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example: 

Given the 2D grid:

INF  -1  0  INF 
INF INF INF -1
INF -1 INF -1
0 -1 INF INF

After running your function, the 2D grid should be:

3  -1   0   1   
2 2 1 -1
1 -1 2 -1
0 -1 3 4

Analysis

We can set all the gates as the roots of BFS and push them to the queue. And set each nodes adjacent to the current node to the current node’s value plus one.

In this problem, if we use naive BFS, all the gates should be implemented BFS in \(O(n^2)\) time. So the worst cast time will be \(O(n^4)\).

But the Multi-end BFS is very stable and its time is always \(O(n^2)\).

Solution

// Set gate as the root of BFS
// Multi-end BFS

class Solution {
    public void wallsAndGates(int[][] rooms) {
        Queue<int[]> q = new LinkedList<>();
        int[][] dir = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
        for(int ii = 0; ii < rooms.length; ii++)
        {
            for(int jj = 0; jj < rooms[0].length; jj++)
            {
                if(rooms[ii][jj] == 0)
                {
                    q.add(new int[]{ii, jj});
                }
            }
        }
        int[] temp;
        while(q.size() > 0)
        {
            int qsize = q.size();
            for(int j = 0; j < qsize; j++)
            {
                temp = q.poll();
                for(int i = 0; i < 4; i++)
                {
                    int nexti = temp[0] + dir[i][0];
                    int nextj = temp[1] + dir[i][1];
                    if(nexti >= 0 && nexti < rooms.length && nextj >= 0 && nextj < rooms[0].length && rooms[nexti][nextj] == Integer.MAX_VALUE)
                    {
                        rooms[nexti][nextj] = rooms[temp[0]][temp[1]] + 1;
                        q.add(new int[]{nexti, nextj});
                    }
                }                
            }
        }
    }
}

Reference

[1] https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1373/discuss/72748/Benchmarks-of-DFS-and-BFS

Leave a Reply

Your email address will not be published. Required fields are marked *