경로 알고리즘 : 그리드의 A에서 B까지의 경로가 주위를 돌고 있는지 확인하는 방법은 무엇입니까?

Question

A에서 B로 그리고 A로 돌아가는 경로가 무엇이든 돌아 다니는지 알아야합니다.

예 : 경로는 APPPPPBA입니다. X 주위를 돌아서 결과는 TRUE입니다.

XXXXXXXX 
XPPPXXXX 
XBXPXXXX 
XAPPXXXX 
XXXXXXXX 

경로는 APPPPPPPBA입니다. 그것은 어떤 X의 주위에 가지 않으므로 결과는 틀립니다.

XXXXXXXX 
XPPPXXXX 
XBPPXXXX 
XAPPXXXX 
XXXXXXXX 

Answer 1

격자 주위에 추가로 X 개의 경계선을 추가하십시오. 타일을 "경로를 둘러 쌈"으로 표시하려면이 타일 중 하나에서 시작하여 flood fill을 수행하십시오. 이후에 모든 타일이 홍수로 채워지거나 경로의 일부인 경우 경로가 아무 것도 둘러싸 지 않습니다. (경계선은 두 경로로 그리드를 자르는 상황을 처리하는 데 필요합니다. 또는 각 가장자리 타일에서 채우기를 시작할 수 있습니다.)