title: Calculate minimum distance in a straight line using BFS
body: <p>Trying to solve <a href="https://www.hackerrank.com/challenges/castle-on-the-grid" rel="nofollow">this problem</a> using BFS. </p>
  
  <p>Problem Gist: Initial and final position is given for a <a href="https://en.wikipedia.org/wiki/Rook_(chess)" rel="nofollow">rook</a> placed in a matrix. You are required to find out minimum number of steps for rook to reach final position. Some position marked with "X" shouldn't be crossed, whereas "." are the allowable positions.</p>
  
  <pre><code>Matrix:
  .X.
  .X.
  ...
  source position: 0,0
  target position: 0,2
  answer:3 (0,0) -&gt; (2,0) - &gt; (2,2) -&gt; (0,2)
  </code></pre>
  
  <p>My solution basically does below:
  I start doing BFS from source node and after I dequeue the node I am adding all the vertical and horizontal nodes in memory with the current distance of that node plus 1. After that I am checking if the destination node is present in memory and if it is present I am returning that distance.</p>
  
  <p>This below solution is not working in some of the cases. Any suggestions?</p>
  
  <pre><code>def update_distance(memoize_dist, current, n, count, matrix):
    directions = [1, -1, 1, -1]
    current_x, current_y = current
    temp_x, temp_y = current
    for direction in directions:
      while temp_x &lt; n and temp_x &gt;= 0:
        temp_x += direction
        temp = (temp_x, current_y)    
        if temp_x &gt;= n or temp_x &lt; 0 or matrix[temp_x][current_y] == 'X':
          temp_x, temp_y = (current_x, current_y)
          break                   
        if temp not in memoize_dist.keys():
          memoize_dist[temp] = count
    for direction in directions:
      while temp_y &lt; n and temp_y &gt;= 0:
        temp_y += direction
        temp = (current_x, temp_y)
        if temp_y &gt;= n or temp_y &lt; 0 or matrix[current_x][temp_y] == 'X':
          temp_x, temp_y = (current_x, current_y)
          break       
        if temp not in memoize_dist.keys():               
          memoize_dist[temp] = count
  
  def get_shortest(n, src, target, matrix):
      queue, memoize, memoize_dist = [], {}, {}
      queue.append((src[0], src[1], 0))
      memoize_dist[(src[0], src[1])] = 0
      while len(queue):
        x, y, count = queue.pop(0)
        cur = (x, y)
        if cur in memoize.keys() and memoize[cur] != -1:
          continue
        memoize[cur] = 1          
        update_distance(memoize_dist, cur, n, count+1, matrix)    
        if target in memoize_dist.keys():
          return memoize_dist[target]
        directions = [1, -1, 1, -1]
        for direction in directions:
          if cur[0]+direction &lt; n and cur[0]+direction &gt;= 0 and matrix[cur[0]+direction][cur[1]] != 'X':
            queue.append((cur[0]+direction, cur[1], memoize_dist[(cur[0]+direction, cur[1])]))
          if cur[1]+direction &lt; n and cur[1]+direction &gt;= 0 and matrix[cur[0]][cur[1]+direction] != 'X':
            queue.append((cur[0], cur[1]+direction, memoize_dist[(cur[0], cur[1]+direction)]))
  
  n = int(input())
  matrix = []
  for i in range(n):
      matrix.append(input())
  start_x, start_y, dest_x, dest_y = map(int, input().split(" "))
  print(get_shortest(n, (start_x, start_y), (dest_x, dest_y), matrix))
  </code></pre>