題目鏈接：https://leetcode.cn/problems/kjpLFZ/

題目大意：給一個矩陣matrix[][]，元素為小寫英文字母。給一個字符串mantra，求從矩陣的(0,0)位置開始，可以移動（上下左右）或者提取字母，求組成字符串的最小【移動+提取次數】

思路：顯然是BFS，然而BFS無法保證結果“最小”。一個例子就是，如果要找speed這個詞，然而矩陣第一行是speeabd，第一列是speedxxx，那么如果在BFS時先按行找，就會陷入陷阱，因為明顯按列找才是最短的。

看了題解才知道有一種“3維BFS”的存在。類似于一個魔方，在每一層進行BFS，上面一層滿足了條件（找到下一個字母）后才能往下一層轉移。轉移了并不會終止上一層的BFS，這樣就避免了遺漏可能的最小的其他路徑。

并且還學到了新的【上下左右偏移】的寫法，只用到一個長為5的一維數組dir就行。

完整代碼

class Solution {
public:int extractMantra(vector<string>& matrix, string mantra) {int n = matrix.size(), m = matrix[0].length(), k = mantra.length();bool known[101][101][101] = {};const int dir[] = {0, 1, 0, -1, 0};queue<tuple<char, char, char>> q;q.emplace(0, 0, 0);known[0][0][0] = true;int ans = 0;while (!q.empty()) {for (int i = q.size(); i > 0; i--) {auto x = get<0>(q.front());auto y = get<1>(q.front());auto z = get<2>(q.front());q.pop();if (z == k)return ans;if (mantra[z] == matrix[x][y] && !known[x][y][z+1]) {q.emplace(x, y, z+1);known[x][y][z+1] = true;continue;}for (int j = 0; j < 4; j++) {auto tx = x + dir[j];auto ty = y + dir[j+1];if (tx >= 0 && tx < n && ty >= 0 && ty < m && !known[tx][ty][z]) {q.emplace(tx, ty, z);known[tx][ty][z] = true;}}}ans++;}   return -1;}
};