SPOJ 비트 맵

Question

파이썬을 사용하여 spoj 문제를 해결하려고합니다. 내 알고리즘은 O (N^2)해야하지만, 여전히 TLE는
내 방법은 단지 멀티 소스 BFS이다 ... 리턴된다.

1. "ANS"
2. 인쇄 ANS

문제 링크라는 이름의 2D 목록으로 최단 거리를 저장, 각각 '1'의 모든 1

실행 BFS의 위치를 ​​찾기 : http://www.spoj.pl/problems/BITMAP/

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 < num_element: 
      new_list = [] 
      for node in front: 
       i = node[0] 
       j = node[1] 
       new_distance = ans[i][j] + 1 
       if(i> 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< 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 > 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 < 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() 

Answer 1

감사합니다. 마침내 C++에서 동일한 알고리즘을 구현하고 받아들입니다! 문제는 2 차원 배열이 파이썬에 적합하지 않은 것 같습니다.

Answer 2

이는 맨해튼 메트릭과 distance transform를 계산하는 것이 필요하다. This article은 유클리드 메트릭에 대한 선형 알고리즘 (O (행 * cols) 알고리즘)을 나타냅니다 (그러나 Manhattan 역시 언급 됨).