동굴에있는 도둑이 퍼즐을 쓰고 있습니다.

Question

내 친구가이 코딩 퍼즐을 나에게 공유했는데 막혔습니다. 여기에 퍼즐이 있습니다 :

동굴이 배열 인덱스 으로 표시되는 동굴과 도둑의 배열을 상상해보십시오. 매일 도둑은 동굴을 방향으로 움직일 수 있으며 이전에 방문한 동굴로 돌아갈 수는 있지만 을 움직여 야합니다.

확인하려면 동굴 순서로 하루에 하나씩 목록이 제공됩니다. 그 이동으로 적어도 수표 중 하나에서 도둑을 잡을 수 있는지 확인하십시오. 내가 함께 왔어요 무엇

:

동굴 배열을 가정은 0 인덱스입니다. 그런 다음 "경계" 점을 인덱스 1과 len (동굴) - 2로 정의 할 수 있습니다. 경계 지점에서 시작하고 다음 경계 지점까지 선형으로 스윕 한 다음 경계 지점을 다시 확인하십시오 하나에 도달 한 후 을 다른 경계 지점으로 되돌려 보내면 도둑을 잡을 수 있습니다. 예를 들어 우리 동굴의 길이가 5 인 경우 :

123321 및 123123은 도둑이 모두 잡히는 것을 보장합니다.

그러나이 템플릿은 완전한 템플릿이라고 생각하지 않으며 여전히 작동하는 다른 스키마가있을 수 있습니다. 누군가 다른 아이디어가 있는지 궁금 해서요! 다음

Answer 1

한가지 방법은, 그 각 단계 i 위해 포착되지 않고 수 도둑위한 가능한 위치들의 어레이를 정의들을 해결 :

Stop clauses and boundaries: 
thief[-1][i] = true (for all i in [0,NUM_CAVES)) 
thief[k][-1] = false (for all k) 
thief[k][NUM_CAVES] = false (for all k) 
Step: 
thief[k][i] = check[k] != i && (thief[k-1][i-1] || thief[k-1][i+1]) 

직관 스텝 k에서
, 도둑은 수색중인 동굴에서 잡을 수 없습니다 (이것은 check[k] != i 부분입니다).
또한 이전 라운드 (두 번째 부분 인 thief[k-1][i-1] || thief[k-1][i+1])의 인접한 동굴에있을 수 없다면 그는 동굴 i에있을 수 없습니다.

이

는 n 동굴 수 있고 m 제공된리스트의 길이 O(n*m) 시간에 Dynamic Programming으로 해결 될 수있다.

테이블을 계산 완료, 대답은 기본적으로 :

의미

NOT(thief[m][0] || thief[m][1] || ... || thief[m][n-1]) 

, 도둑이 어떤 동굴에있을 수 없습니다, 그는 잡힌되지 않은 가정.