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