Math
Ширина і глибина
Два однакові лабіринти, два обходи, клітинка за такт. Шар, на якому ширина знайшла клітинку, дорівнює найкоротшому шляху — це тотожність. Глибина не коротша ніколи, а наскільки довша — залежить від того, куди йти.
Що відбувається
Один лабіринт, два пошуки, одне відкриття за крок. Ліворуч пошук у ширину бере клітинки з ЧЕРГИ — першим прийшов, першим пішов, — тому розходиться кільцями, і кільце, на якому він знаходить клітинку, — її найкоротша відстань: у незваженому лабіринті пошук у ширину Є пошуком найкоротшого шляху. Праворуч пошук у глибину бере їх зі СТЕКУ — останнім прийшов, першим пішов, — тому пірнає в перший поворот і відступає лише з глухого кута; його маршрут — просто маршрут, без обіцянки стислості. Сині клітинки чекають у структурі, сіро-зелені завершені, золотий квадрат розкривається, а під кожним лабіринтом перелічено справжні чергу і стек, наступна клітинка першою. Малюйте стіни, натискайте в лабіринті, щоб передбачити, куди пошук піде далі, і робіть крок. Якщо ціль відрізана стінами, обидва пошуки закінчуються на краю компоненти старту й прямо про це кажуть.
Рівняння модуля
Рівняння лабіринт на сітці m x m, чотири сусіди, старт у лівому верхньому куті; порядок сусідів: вгору, вправо, вниз, вліво - однаковий в обох пошуках пошук вшир: шар, на якому знайдено клітинку, І Є довжиною найкоротшого шляху - тотожність, перевірена порівнянням з НЕЗАЛЕЖНОЮ релаксацією до нерухомої точки та, на малих сітках, з повним перебором простих шляхів порожня сітка: відстань до (i, j) = i + j; клітинок на відстані d = min(d, m−1) − max(0, d−m+1) + 1; найширший шар = m при d = m − 1; дальній кут = 2(m−1) = 40 при m = 21 обидва пошуки охоплюють ОДНУ Й ТУ САМУ множину - компоненту старту, незалежно пораховану лісом неперетинних множин - і кожен дивиться на кожне ребро двічі: 2|E| = 1196 при 21x21 із 20 % стін пошук углиб ніколи не коротший, а наскільки довший, залежить від КЛІТИНКИ: до дальнього кута порожньої сітки він робить ті самі 2(m−1) кроків, до клітинки на один крок нижче за старт йому потрібно 421 крок при m = 21 на порожній сітці дерево пошуку вглиб є ГАМІЛЬТОНОВИМ ШЛЯХОМ - кожна клітинка має щонайбільше одного нащадка, найглибша лежить на глибині m²−1, а парність вирішує, де закінчується змія: (1,0) для парного m, (m−1,0) для непарного m 21x21, 20 % стін, мета в дальньому куті: вшир 40 кроків після перегляду 370 клітинок; вглиб 50 кроків після перегляду 53 - обидва платять, але різною монетою той самий лабіринт, мета в центрі: вшир 20, вглиб 156; а на 297 з 371 досяжних клітинок маршрут пошуку вглиб щонайменше втричі довший
