BFS
BFS + 狀態(tài)壓縮
求最短路徑可以使用BFS，但本題不能使用一般的BFS來求解，因為我們在搜索的時候得記錄當(dāng)前已經(jīng)收集到的鑰匙，即收集狀態(tài)，另外根據(jù)題意可知，與傳統(tǒng)的BFS不同，這里搜索是可以回退的。
根據(jù)題意可知，代表鑰匙和鎖的字母互為大小寫并按字母順序排列，因此我們可以用一個int類型的二進制數(shù)state來表示收集鑰匙的狀態(tài):
- 若二進制中第
k位為1，則表示字母序為k的鑰匙已被收集 - 若二進制中第
k位為0，則表示字母序為k的鑰匙未被收集
其中發(fā)鑰匙種類編號按小寫字母順序，從0開始進行先后劃分，a 對應(yīng)0, b 對應(yīng)1 .... ,例如當(dāng)前收集到的鑰匙為a, c，d，則對應(yīng)的二進制為1101
這樣，我們就可以通過位運算很容易更新鑰匙收集狀態(tài)和鑰匙開鎖檢測：
鑰匙檢測:
(state >> k) & 1,k表示編號為k的鑰匙，如果位運算結(jié)果為1則表示當(dāng)前已收集該鑰匙，結(jié)果為0表示未收集該鑰匙。更新鑰匙收集狀態(tài)：
state = state | (1 << k),將state第k位設(shè)置位1，表示已經(jīng)收集到該鑰匙。
有了記錄鑰匙收集狀態(tài)的方法，我們接下來進行BFS:
- 首先定義用來記錄路徑距離的數(shù)組
dist，與傳統(tǒng)的BFS不同，我們除了要表示當(dāng)前位置的坐標(biāo)(i, j)外，我們還需要表示當(dāng)前位置的鑰匙收集狀態(tài)，因為每次經(jīng)過同一個位置時可以有多個鑰匙收集狀態(tài)。我們用一個三維數(shù)組dist[i][j][s]來記錄在(i, j)位置且鑰匙收集狀態(tài)為s時的最短路徑距離。將起點，鑰匙手機狀態(tài)為0的dist初始化為0，其他初始化為無窮大。 - 遍歷棋盤，找到起點位置，初始化起點的
dist為0，然后將起點信息加入隊列，隊列維護的是三元組{i, j , s}的狀態(tài)。 - 進行四聯(lián)通方向遍歷
- 如果遇到墻，該遍歷方向違法，
continue - 如果遇到鎖，且當(dāng)前收集的鑰匙無法開始，改遍歷方向違法,
continue - 如果是鑰匙且未收集，更新鑰匙收集狀態(tài)
ns - 如果
dsit[x][y][s] + 1 > dsit[nx][ny][ns],說明改遍歷方向不是最短路徑，不符合題意,continue - 否則，我們更新
dsit[nx][ny][ns] = dsit[x][y][s] + 1并將{nx, ny, ns}加入隊列
- 如果遇到墻，該遍歷方向違法，
