# Optimization of BFS for finding minimum distances between elements of a grid

This is from HackerRank - Travel Diaries.

Given a grid of 0s,1s and 2s we need to find minimum distance of each 1 from 2 going through 1s only. (See 1 as land, 0 as ocean, 2 as food, need to find closest food for each tile of land where boats don't exists).

class Queue:
def __init__(self):
self.items = []
def empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
try:
return self.items.pop()
except: return False
def size(self):
return len(self.items)

grid = list()
distances = list()
tocheck = Queue()

for i in range(n):
toapp = []
for j in range(m):
c = grid[i][j]
if c == 2:
toapp.append(0)
tocheck.enqueue((i,j))
else: toapp.append(m*n + (c-1)*m*n-1)
distances.append(toapp)

c = tocheck.dequeue()
while c:
x,y = c
for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if 0 <= i < n:
if 0 <= j < m:
if grid[i][j] == 1:
if distances[x][y]+1 < distances[i][j]:
distances[i][j] = distances[x][y] + 1
grid[i][j] = 2
tocheck.enqueue((i,j))
c = tocheck.dequeue()

maxi = max([max(i) for i in distances])
if maxi == m*n-1: maxi = -1
print(maxi)


Explanation:

Firstly, a pretty standard class implementing queues (Can't use builtin module for some reason). n,m = #rows, #cols

Next, a grid containing values and a grid containing distances is created. If the value is 2, then distance matrix contains 0. If value is 1, then distance is m*n-1 (larger than maximum possible distance). If value is 0, then distance is -1 (not possible). Also, every location containing 2 is also stored separately in a queue

Main BFS part: Dequeue a location. Check if all Neighbours all valid entries in matrix containing 1. If the distance of this neighobour is strictly greater than the current locations distance + 1, then update the neighbour's value to 2, distance to current distance + 1 and queue it. Repeat till queue is empty.

Any suggestions for optimization? (I realize my code has 0 comments but then again I didn't know I'd spend over 4 hours on this)

For a 1000 x 1000 grid this takes way over 5 seconds which is the required time limit. For a 100 X 100 grid it takes about 0.23 seconds on i3-4005U 1.7 Ghz.

• Please, follow PEP-8 (put spaces around <=, <, >, >=; avoid compound statements) and use built-in function max to found maximum value in array – belkka Mar 3 '19 at 17:57
• It is very convenient to use readline() function that returns list(map(int,input().split())). Could you rewrite the code using this function and edit the question to improve readability, since you are asking about optimization and not code style? – belkka Mar 3 '19 at 18:02
• @belkka done both – Anvit Mar 4 '19 at 3:13