【3维BFS】个人练习-Leetcode-LCP 79. 提取咒文

题目链接：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;
    }
};