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) def readline(): return map(int,input().split(' ')) n,m = readline() grid = list() distances = list() tocheck = Queue() for i in range(n): grid.append(list(readline())) 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)
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.