도넛 메이즈

코드 출현 2019 20일차

과제: X에 대해 풀기 여기서...

1 부

X = the number of steps it takes to get from the open tile marked AA to the open tile marked ZZ

2 부

X = the number of steps it takes to get from the open tile marked AA to the open tile marked ZZ, both at the outermost layer

예시 입력

         A           
         A           
  #######.#########  
  #######.........#  
  #######.#######.#  
  #######.#######.#  
  #######.#######.#  
  #####  B    ###.#  
BC...##  C    ###.#  
  ##.##       ###.#  
  ##...DE  F  ###.#  
  #####    G  ###.#  
  #########.#####.#  
DE..#######...###.#  
  #.#########.###.#  
FG..#########.....#  
  ###########.#####  
             Z       
             Z       

다음을 나타냅니다.

도넛 모양의 미로

# s는 벽

. s는 열린 공간입니다

대문자 쌍은 시작(AA), 끝(ZZ) 또는 포털

입니다.

포탈은 포탈에 들어가기 전에 다른 쪽에서 나간 후 타일로 사용자를 이동시킵니다

.

1 부

또 다른 길 찾기 퍼즐... 훌륭합니다.

최단 경로? 아니면 경로만?

점 연결 시도 중...오류, 포털

마지막 동기 부여를 위한 규칙 참조

또 다른 길 찾기 퍼즐... 훌륭합니다.

마지막이 딱 이틀 전!

정규 표현식과 마찬가지로 이러한 유형의 퍼즐을 보다 자신감 있게 시도할 수 있도록 길 찾기 알고리즘을 공부해야 한다고 생각합니다

.

최단 경로? 아니면 경로만?

첫 번째 예에는 AA에서 ZZ까지 두 개의 경로가 있으며 하나는 더 짧습니다

.

두 번째 예에는 하나의 경로가 있습니다

.

챌린지 질문에 '최단' 경로가 언급되지 않음

AA에서 ZZ까지의 경로는 하나뿐이라고 믿게 되었습니까?

아마도 신중한 연구와 제거 과정을 통해 알아낼 수 있을 것입니다!

점을 연결하려는 중...오류, 포털

신중한 수동 시각적 순회 후 AA에서 ZZ로의 경로를 확인했습니다.

AA
 LU
  OP
   VR
    MU
     MH
      NH
       TJ
        KJ
         NI
          DR
           QC
            ME
             HK
              KA
               QN
                RB
                 KM
                  ZZ

이제 점을 셀 시간입니다.

올바른 포털 사이의 점을 세는 중...

시도 1

AA +9
 LU +55
  OP +47
   VR +51
    MU +49
     MH +69
      NH +75
       TJ +56
        KJ +49
         NI +68
          DR +49
           QC +59
            ME +53
             HK +61
              KA +61
               QN +85
                RB +69
                 KM +65
                  ZZ
1030 TOO HIGH

시도 2
더 짧은 경로 식별

ZZ +5
 XF +49
  HU +65
   QL +57
    QH +63
     QD +63
      CA +87 
       AO +7
        MH +49
         MU +51
          VR +47
           OP +55
            LU +9
             AA
607 TOO HIGH

시도 3
더 짧은 경로 식별

ZZ +5
 XF +49
  HU +65
   QL +57
    QH +63
     QD +63
      CA +87 
       AO +57
        XB +63
         WY +39
          WC +47
           AA

595 TOO HIGH

시도 3에서 설명한 것보다 더 짧은 경로는 없습니다.

하위 경로 중 하나를 잘못 계산했을 수 있습니까?

다시 역순으로 세어보니

AA +47
 WC +39
  WY +63
   XB +57
    AO +87
     CA +63
      QD +63
       QH +57
        QL +65
         HU +49
          XF +5
           ZZ
595 SAME

음, 쉿.

동기 부여의 마지막 불꽃에 대한 규칙 참조

포털 바로 앞에 있는 점이 계산되지 않는 것 같습니다

.

그러나 포털에서 포털로의 이동은 계산됩니다

.

이것은 내가 1만큼 벗어났다는 것을 의미할 수 있습니다. AA 바로 앞에 있는 점을 세어서는 안 됩니다

.

시도 4

  AA +46
+1 WC +38
 +1 WY +62
  +1 XB +56
   +1 AO +86
    +1 CA +62
     +1 QD +62
      +1 QH +56
       +1 QL +64
        +1 HU +48
         +1 XF +4
             ZZ
594

정답이었습니다!

2 부

이런. 재귀. 그리고 길 찾기.

고맙지 만 사양 할게.

내 성취를 축하해

파트 1을 풀었습니다...4번의 실패에도 불구하고!

규칙을 공부하는 데 도움이 됩니다.

그렇지 않으면, 당신은 떨어져 있을 수 있습니다.