행렬 알고리즘의 신호 도달 범위

Question

알고리즘 문제를 발견했으며 가능한 해결책을 생각해 보았습니다. 그러나 "직관적 인"알고리즘에 대해 생각해 볼 수 있습니다. 누군가가 나를 도와 줄 수 있는지 보겠습니다.

다음은 우리가 이고 빈 공간이 .이고 벽이 % 인 것으로 나타났습니다. n 단계/셀 범위의 매트릭스 안에있는 (i,j)에 "라우터"(R으로 표시)를 배치 할 수 있습니다. 단계는 위/아래/왼쪽/오른쪽 만있을 수 있다고 생각하십시오. 라우터 범위를 확인하는 가장 효율적인 방법은 무엇입니까?

예 (N = 4)

. . . . . . . . . . 
. . % % . . . . . . 
. . % . . . % . . . 
. . . . R . % . . . 
. . % . . . % . . . 
. . % . . . . . . . 

한가 지 (#마르크이 범위를 신호) 내가 조사하고 홍수가 알고리즘을 기입 발견했습니다

. . . # # # . . . . 
. . % % # # # . . . 
. # % # # # % . . . 
# # # # R # % . . . 
. # % # # # % . . . 
. . % # # # # . . . 

, 내가 그것을 사용할 수있는 것 같아요 이미 재귀 적으로 사용한 단계를 확인하기위한 추가 매개 변수입니다. 더 효율적인 알고리즘을 아십니까?

일부 코드를 작성하려면 원하는 언어를 자유롭게 사용하십시오. 미리 감사드립니다.

Answer 1

최선의 방법은 BFS를 사용하는 것입니다. 기본적으로 대기열을 사용하여 계층별로 노드를 방문합니다.

는() 0,0 (로 R을 고려)이 같은 세포를 방문 BFS를 사용 :

t = 0 - Queue = {(0,0)} 
For each element in query, visit north, east, west, south if not 
visited and not wall 
For (0, 0) -> Visit (1, 0), (0, 1), (-1, 0), (0, -1) 
. . . . . . . . . . 
. . % % . . . . . . 
. . % . . . % . . . 
. . . . R . % . . . 
. . % . . . % . . . 
. . % . . . . . . . 

t = 1 Queue = {(1, 0), (0, 1), (-1, 0), (0, -1)} 
For each element in query, visit north, east, west, south if not visited and not wall 
For (1, 0) -> Visit (2, 0), (1, 1), (1, -1) 
For (0, 1) -> Visit (0, 2), (-1, 1) 
For (-1, 0) -> Visit (-1, 0), (-2, 0) 
For (0, -1) -> Visit (-1, -1), (0, -2) 

. . . . . . . . . . 
. . % % . . . . . . 
. . % . # . % . . . 
. . . # R # % . . . 
. . % . # . % . . . 
. . % . . . . . . . 

t = 2 and so on 
. . . . . . . . . . 
. . % % # . . . . . 
. . % # # # % . . . 
. . # # R # % . . . 
. . % # # # % . . . 
. . % . # . . . . . 


t = 3 
. . . . # . . . . . 
. . % % # # . . . . 
. . % # # # % . . . 
. # # # R # % . . . 
. . % # # # % . . . 
. . % # # # . . . .