그리드가 있고 100만 행과 100만 열이 있고 차단된 셀 목록도 하나 있다고 가정합니다. 이제 소스 사각형에서 시작하여 대상 사각형에 도달하려고 합니다. 각 이동에서 우리는 차단된 셀의 주어진 목록에 없는 그리드의 위, 아래, 왼쪽, 오른쪽 인접 사각형으로 걸어갈 수 있습니다.
일련의 이동을 통해 목표 사각형에 도달할 수 있는지 여부를 확인해야 합니다.
따라서 입력이 차단됨 =[[0,1],[1,0]], 소스 =[0,0], 대상 =[0,3]인 경우 출력은 False
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
차단됨 :=차단된 모든 셀 집합을 만듭니다.
-
하나의 메소드 dfs()를 정의하십시오. x, y, target 및 see가 필요합니다.
-
(x,y)가 그리드 범위에 있지 않거나 (x,y)가 차단되거나 (x,y)가 표시되는 경우
-
거짓을 반환
-
-
-
본 항목에 (x,y) 추가
-
본 크기> 20000 또는 (x,y)가 대상인 경우
-
true를 반환
-
-
dfs(x+1,y,target,seen) 또는 dfs(x-1,y,target,seen) 또는 dfs(x,y+1,target,seen) 또는 dfs(x,y-1,target, 본)
-
return dfs(source[0], source[1], target, empty set) 및 dfs(target[0], target[1], source, empty set)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def isEscapePossible(self, blocked, source, target): blocked = set(map(tuple, blocked)) def dfs(x, y, target, seen): if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return False seen.add((x, y)) if len(seen) > 20000 or [x, y] == target: return True return dfs(x + 1, y, target, seen) or \ dfs(x - 1, y, target, seen) or \ dfs(x, y + 1, target, seen) or \ dfs(x, y - 1, target, seen) return dfs(source[0], source[1], target, set()) and dfs(target[0], target[1], source, set()) ob = Solution() print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))
입력
[[0,1],[1,0]], [0,0], [0,3]
출력
False