8 방향의 행렬 미로

Question

행렬에 1과 0이 주어지며, 여기서 0은 빈 경로를 나타내고 1은 차단 된 영역을 나타냅니다. 8 가지 방향 중 하나로 이동할 수 있습니다. 출발지에서 목적지까지의 최단 경로 찾기.

내가 가지고 올 수 있었다 솔루션 여기서 시작 정점에서 dp[i,j] 저장의 최소 거리 :

recursion(int i, int j , int sum) 
{ 

    if(!issafe(i,j) || isvisited[i,j]) // within bounds 
    return ; 

    if(matrix(i,j)==0)//blocked 
    return ; 

    isvisited[i,j]=true; 

    dp[i,j] = min(dp[i,j] , sum); 
    // directions have usual meaning 

    recursion(east ,sum+1); // i , j+1 
    recursion(north , sum+1); //i-1 , j 
    recursion(west , sum+1); 
    recursion(south , sum+1); 
    recursion(north-east , sum+1); 
    recursion(north-west , sum+1); 
    recursion(south-east , sum+1); 
    recursion(south-west , sum+1); 

    isvisited[i,j]=false; 

return; 
} 

지금 내 의심의 여지가 우리가 8 개 위치에서 [I, J]를 도달 할 수 있다고 생각합니다. 내가 1 순위에서 도달하자 마자 말하십시오. 경로는 x 단위입니다. 재귀 적으로 이웃 노드를 바로 확인합니다. 자, 나는 2 번 경로에서 와서 그 분을 찾는다. path (이전 x)는 이제 y가 아닌 x이며 이제 다시 재귀 적으로 확인됩니다. 따라서 1 단계에서 추가 계산을 수행하지 않아도됩니다. 내가 분을 찾은 후에 만 ​​재귀 적으로 이웃을 확인하는 방법이 있습니까? 경로 (현재 8 개 지점 모두에서 도달 가능)?

Answer 1

이것은 가중치가없는 그래프에서 shortest path problem이며 BFS으로 해결할 수 있습니다.

여기에서 그래프 G=(V,E) 곳에 접근 방식은 부가 데이터를 사용 DFS의 변형

• V = { all cells in the matrix}
• E= { (v1,v2) | can move from cell v1 to cell v2 }

참고 [dp 배열]

---

고급 방법은 bi-directional 검색 또는 A* algorithm (경험적으로는 manhattan distances)입니다. 의사 코드 BFS

---

이 용액

BFS(source,destination): 
    visited <- {} //empty dictionary 
    queue <- new queue 
    queue.add (source) 
    visited.add(source,null) 
    while (! queue.isEmpty()): 
     v <- queue.pop() 
     if v == destination: 
     return getPath(visited, v) 
     for each edge (v,u): 
     if u is not a key in visited: 
      visited.add(u,v) 
      queue.add(u) 

getPath(visited,v): 
    list <- new linked list 
    while (v != null): 
     list.addFirst(v) 
     v <- visited.get(v) 
    return list 

시간 복잡도는 O(min{|V|,8^d}) 인 - d 최단 경로의 길이이고, |V| 매트릭스 셀의 수이다.