Algorithms 2 - Mapping Zeroes [Code]

The king of Sikinia was very satisfied with your work documenting his kingdom's wealth distribution. As a result, he has put you in charge of improving the country's road system. Various portions of the country are well reachable from existing roads, while others are cut off from the transportation network. Given a a map of a particular region, devise an algorithm for computing whether it needs new roads to be built!

Problem: Given a $m\times n$ binary array $A$, write code to determine whether each 0 is 'connected' to every other 0 by going up, down, left, or right in $O(m\times n)$ time. You may assume that the array contains at least one 0 and is properly formatted.

Example:

//Valid array.
1 1 1 0 0 0
0 0 0 0 1 1
1 1 0 0 1 0
1 0 0 0 0 0
//Invalid array.
1 1 1 0 0 0
0 0 0 1 1 1
1 1 0 0 1 0
1 0 0 0 0 0
Solution.

This problem is a standard graph-connectivity problem using breadth-first-search. For this solution, I will use Python. (Mostly for practice!)

First, we find the first coordinate of $A$ with a 0, and assign that value to $p$.

p = [0, 0]
for i in range(0, m):
	for j in range(0, n):
    	if A[i][j] == 0:
        	p = [i, j]
            break

Let's also create a 2D boolean array to check what 0's we've visited.

not_visited = [[True for j in range(n)] for i in range(m)]

We'll also create a method to get a list of all of a point's neighbors.

#x is a coordinate of form [row, col]
def neighbors(x):
	ne = []
    i, j = x[0], x[1]
    if x[0] > 0 and A[i - 1][j] == 0:
    	ne.append([i-1, j])
    if x[1] > 0 and A[i][j-1] == 0:
    	ne.append([i, j-1])
    if x[0] < m-1 and A[i + 1][j] == 0:
    	ne.append([i+1, j])
    if x[1] < n-1 and A[i][j+1] == 0:
    	ne.append([i, j+1])
    return ne
    	

Now that we have our coordinate, we can iteratively perform BFS using a list as a queue.

from collections import deque

q = deque([p])
while len(q) > 0:
	p = q.popleft()
    not_visited[p[0]][p[1]] = False
    for ne in neighbors(p):
    	if not_visited[ne[0]][ne[1]]:
        	q.append(ne)

Once this operation completes, we compare the locations of the 0's in $A$ with the values of $visited$.

for i in range(0, m):
	for j in range(0, n):
    	if not_visited[i][j] and A[i][j] == 0:
        	return False
return True

Tada, we're done!