Однозначно описати поточне положення героя недостатньо: потрібно знати, які саме k\;(0\le k\le 6) скарабеїв уже зібрано. Зафіксуємо це бітовою маскою mask\in[0,2^{6}), де $i$-й біт установлено, якщо скарабей 'a'+i вже в Індіани. Таким чином, стан — це трійка

Шукатимемо найкоротший шлях звичайним пошуком у ширину (BFS), бо всі переходи рівновагові (вага $=1$).

Зі стану (x,y,mask) розглядаємо чотири сусідні клітинки (x',y'):

• якщо там # — пропускаємо;

• якщо A...F, позначимо символ c, індекс i=c-\texttt{A}; перехід можливий лише, якщо \bigl(mask\ \&\ (1\ll i)\bigr)\neq0;

• якщо a...f, аналогічний індекс i=c-\texttt{a}; у новому стані mask' = mask \mid (1\ll i);

• якщо . — переходимо без зміни маски.

• Черга BFS містить стани; починаємо з (1,1,0).

• Тривимірний масив dist[x][y][mask] зберігає вже знайдену найкоротшу відстань; ініціалізується $\infty$.

Після вичерпання черги:

Якщо \texttt{ans}<\infty, це відповідає мінімальній кількості кроків; інакше виводимо $-1$. Загальна часова складність O(2^6nm).