title: SPOJ Bitmap (BFS)
body: <p>I try to solve the spoj problem using <strong>python</strong>. My algorithm should be only <strong>O(n^2)</strong>, but still <strong>TLE</strong> is returned...<br>
  My method is just a <strong>multiple source BFS</strong>.  </p>
  
  <ol>
  <li>Find out the position of all 1  </li>
  <li>Run BFS on each '1', store the shortest distance into an 2D list named "ans"</li>
  <li>print ans</li>
  </ol>
  
  <p>problem link: <a href="http://www.spoj.pl/problems/BITMAP/" rel="nofollow">http://www.spoj.pl/problems/BITMAP/</a></p>
  
  <pre><code>if __name__ == '__main__':
      n = int(input())    #reading number of test cases
      for k in range(n): 
          (row, col) = input().split()    #row and col
          row = int(row)
          col = int(col)
          #store the bitmap
          bitmap = []
          for i in range(row):
              line = input()
              bitmap.append(line)
          ans = [[False for i in range(col)] for j in range(row)]     #init a 2d array to store answer
          front = []
          num_element = row*col
          processed = 0
          for i in range(row):
              for j in range(col):
                  if(bitmap[i][j] == '1'):
                      ans[i][j] = 0
                      front.append((i,j))
                      processed = processed +1
          while processed &lt; num_element:
              new_list = []
              for node in front:
                  i = node[0]
                  j = node[1]
                  new_distance = ans[i][j] + 1
                  if(i&gt; 0 and ans[i-1][j] is False):
                      ans[i-1][j] =new_distance                    
                      new_list.append((i-1,j))
                      processed = processed +1
                  if(i&lt; row -1 and ans[i+1][j] is False):
                      ans[i+1][j] =new_distance
                      new_list.append((i+1,j))
                      processed = processed +1
                  if(j &gt; 0 and ans[i][j-1] is False):
                      ans[i][j-1] =new_distance
                      new_list.append((i,j-1))
                      processed = processed +1
                  if(j &lt; col -1 and ans[i][j+1] is False):
                      ans[i][j+1] =new_distance
                      new_list.append((i,j+1))
                      processed = processed +1
              front = new_list
          #print the answer
          for line in ans:
              s = map(str, line)
              print(" ".join(s))
          input()
  </code></pre>