首页算法

LCP 79. 提取咒文

难度中等

随着兽群逐渐远去，一座大升降机缓缓的从地下升到了远征队面前。借由这台升降机，他们将能够到达地底的永恒至森。
在升降机的操作台上，是一个由魔法符号组成的矩阵，为了便于辨识，我们用小写字母来表示。 matrix[i][j] 表示矩阵第 i 行 j 列的字母。该矩阵上有一个提取装置，可以对所在位置的字母提取。
提取装置初始位于矩阵的左上角 [0,0] ，可以通过每次操作移动到上、下、左、右相邻的 1 格位置中。提取装置每次移动或每次提取均记为一次操作。

远征队需要按照顺序，从矩阵中逐一取出字母以组成 mantra ，才能够成功的启动升降机。请返回他们 最少 需要消耗的操作次数。如果无法完成提取，返回 -1 。

注意：

  • 提取装置可对同一位置的字母重复提取，每次提取一个
  • 提取字母时，需按词语顺序依次提取

示例 1：

输入： matrix = ["sd","ep"], mantra = "speed"

输出： 10

解释：如下图所示

img

示例 2：

输入： matrix = ["abc","daf","geg"]， mantra = "sad"

输出： -1

解释：矩阵中不存在 s ，无法提取词语

提示：

  • 0 < matrix.length, matrix[i].length <= 100
  • 0 < mantra.length <= 100
  • matrix 和 mantra 仅由小写字母组成

# BFS 最短路

遍历 mantramantra，求出 mantra[i−1]mantra[i - 1] 到 mantra[i]mantra[i] 的距离

  • 若采用普通 BFS ，由于有多源 dstdst，该结果为离 srcsrc 最近的一个 dstdst 的距离 d[i]d[i]

    若其余的 dstdst 离 mantra[i+1]mantra[i + 1] 的距离 <d[i]+d[i+1]< d[i] + d[i + 1]

    出现了问题、

若对 (0,0)(0, 0) 至 mantra[n−1]mantra[n - 1] 的坐标集合若采用 Dijstra 算法，也不行。因为这是多源路 (有些路径要重复走),

  • 例如: nana

从 (0,0)(0, 0) 出发，保存当前索引 ii，枚举四个方向的相邻点 (cx,cy)(cx, cy)

  • 若 (cx,cy)(cx, cy) 等于 mantra[i]mantra[i]（找到了第 ii 个字符）

    更新 dis[cx][cy][i]=dis[x][y][i−1]+abs(cx−x)+abs(cy−y)dis[cx][cy][i] = dis[x][y][i - 1] + abs(cx - x) + abs(cy - y)

    由于是广搜，此时必然是最短的

    将 (cx,cy,i+1)(cx, cy, i + 1) 压入队列

  • 若 (cx,cy)(cx, cy) 不等于 mantra[i]mantra[i]，将 (cx,cy,i)(cx, cy, i) 压入队列

如下所示有两条路径，由于是广搜，① 必然在 ② 前面

① 0→2s→2p→3e→1p0 \stackrel{2}{\rightarrow} s \stackrel{2}{\rightarrow} p \stackrel{3}{\rightarrow} e \stackrel{1}{\rightarrow} p

② 0→1s→3p→4e→2p0\stackrel{1}{\rightarrow}s \stackrel{3}{\rightarrow} p \stackrel{4}{\rightarrow} e \stackrel{2}{\rightarrow} p

class Solution {
    public int extractMantra(String[] matrix, String mantra) {
        int n = matrix.length;
        int m = matrix[0].length();
        int k = mantra.length();
        char[][] mx = new char[matrix.length][matrix[0].length()];
        for (int i = 0; i < n; i++) {
            mx[i] = matrix[i].toCharArray();
        }
        // 防止重复压入，三个状态
        Set<Pair> visited = new HashSet<>();
        Deque<Pair> queue = new LinkedList<>();
        queue.addLast(new Pair(0, 0, 0));
        int l = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Pair pair = queue.pollFirst();
                if (visited.contains(pair)) {
                    continue;
                }
                visited.add(pair);
                if (pair.i == k) {
                    return l;
                }
                // 说明当前字符的下一个字符对应
                if (mx[pair.x][pair.y] == mantra.charAt(pair.i)) {
                    queue.addLast(new Pair(pair.x, pair.y, pair.i + 1));
                    continue;
                }
                // 枚举四个相邻方向
                for (int i = 0; i < 4; i++) {
                    int cx = dx[i] + pair.x;
                    int cy = dy[i] + pair.y;
                    if (cx >= 0 && cy >= 0 && cx < n && cy < m) {
                        queue.addLast(new Pair(cx, cy, pair.i));
                    }
                }
            }
            l++;
        }
        return -1;
    }
    static int[] dx = new int[]{1, 0, 0, -1};
    static int[] dy = new int[]{0, -1, 1, 0};
}
class Pair {
    int x;
    int y;
    int i;
    public Pair(int x, int y, int i) {
        this.x = x;
        this.y = y;
        this.i = i;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return x == pair.x && y == pair.y && i == pair.i;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y, i);
    }
}