README.md

LCP 56. 信物传送

题目描述

欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。

本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j 列的传送带运作方向，"^","v","<",">" 这四种符号分别表示 上、下、左、右 四个方向。信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。

通关信物初始位于坐标 start处，勇者需要将其移动到坐标 end 处，请返回勇者施法操作的最少次数。

注意：

• start 和 end 的格式均为 [i,j]

示例 1:

输入：matrix = [">>v","v^<","<><"], start = [0,1], end = [2,0]

输出：1

解释： 如上图所示 当信物移动到 [1,1] 时，勇者施法一次将 [1,1] 的传送方向 ^ 从变更为 < 从而信物移动到 [1,0]，后续到达 end 位置 因此勇者最少需要施法操作 1 次

示例 2:

输入：matrix = [">>v",">>v","^<<"], start = [0,0], end = [1,1]

输出：0

解释：勇者无需施法，信物将自动传送至 end 位置

示例 3:

输入：matrix = [">^^>","<^v>","^v^<"], start = [0,0], end = [1,3]

输出：3

提示：

• matrix 中仅包含 '^'、'v'、'<'、'>'
• 0 < matrix.length <= 100
• 0 < matrix[i].length <= 100
• 0 <= start[0],end[0] < matrix.length
• 0 <= start[1],end[1] < matrix[i].length

解法

方法一：双端队列 BFS(0-1 BFS)

每走到一个格子 $(i,j)$，有 $4$ 个方向可以走，如果方向与当前格子的方向相同，那么不需要施法，否则需要施法一次。

因此，我们可以使用 BFS 求出从起点到终点的最短路径。

我们定义一个双端队列 $q$，存储当前可以到达的格子，每次从队首取出一个格子 $(i,j)$，然后向四个方向扩展，如果扩展的格子 $(x,y)$ 不需要施法，那么将其加入队首，否则加入队尾。当我们第一次到达终点时，就得到了最短路径。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

Python3

class Solution:
    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:
        dirs = (-1, 0, 1, 0, -1)
        d = {"^": 0, "v": 2, "<": 3, ">": 1}
        i, j = start
        q = deque([(i, j)])
        m, n = len(matrix), len(matrix[0])
        dist = [[inf] * n for _ in range(m)]
        dist[i][j] = 0
        while 1:
            i, j = q.popleft()
            if i == end[0] and j == end[1]:
                return int(dist[i][j])
            for k in range(4):
                x, y = i + dirs[k], j + dirs[k + 1]
                t = dist[i][j] + int(k != d[matrix[i][j]])
                if 0 <= x < m and 0 <= y < n and t < dist[x][y]:
                    dist[x][y] = t
                    if dist[x][y] == dist[i][j]:
                        q.appendleft((x, y))
                    else:
                        q.append((x, y))

Java

class Solution {
    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        int[] dirs = {-1, 0, 1, 0, -1};
        Map<Character, Integer> d = new HashMap<>(4);
        d.put('^', 0);
        d.put('>', 1);
        d.put('v', 2);
        d.put('<', 3);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {start[0], start[1]});
        int m = matrix.length, n = matrix[0].length();
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, 1 << 30);
        }
        dist[start[0]][start[1]] = 0;
        while (true) {
            int[] p = q.poll();
            int i = p[0], j = p[1];
            if (i == end[0] && j == end[1]) {
                return dist[i][j];
            }
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                int t = dist[i][j] + (k == d.get(matrix[i].charAt(j)) ? 0 : 1);
                if (x >= 0 && x < m && y >= 0 && y < n && t < dist[x][y]) {
                    dist[x][y] = t;
                    if (dist[x][y] == dist[i][j]) {
                        q.offerFirst(new int[] {x, y});
                    } else {
                        q.offerLast(new int[] {x, y});
                    }
                }
            }
        }
    }
}

C++

class Solution {
public:
    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {
        int dirs[5] = {-1, 0, 1, 0, -1};
        unordered_map<char, int> d;
        d['^'] = 0;
        d['>'] = 1;
        d['v'] = 2;
        d['<'] = 3;
        deque<pair<int, int>> q;
        q.emplace_back(start[0], start[1]);
        int m = matrix.size(), n = matrix[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof(dist));
        dist[start[0]][start[1]] = 0;
        while (1) {
            auto [i, j] = q.front();
            q.pop_front();
            if (i == end[0] && j == end[1]) {
                return dist[i][j];
            }
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                int t = dist[i][j] + (k == d[matrix[i][j]] ? 0 : 1);
                if (x >= 0 && x < m && y >= 0 && y < n && t < dist[x][y]) {
                    dist[x][y] = t;
                    if (dist[x][y] == dist[i][j]) {
                        q.emplace_front(x, y);
                    } else {
                        q.emplace_back(x, y);
                    }
                }
            }
        }
    }
};

Go

func conveyorBelt(matrix []string, start []int, end []int) int {
	dirs := [5]int{-1, 0, 1, 0, -1}
	d := map[byte]int{
		'^': 0,
		'>': 1,
		'v': 2,
		'<': 3,
	}
	q := [][2]int{[2]int{start[0], start[1]}}
	m, n := len(matrix), len(matrix[0])
	dist := make([][]int, m)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			dist[i][j] = 1 << 30
		}
	}
	dist[start[0]][start[1]] = 0
	for {
		p := q[0]
		i, j := p[0], p[1]
		if i == end[0] && j == end[1] {
			return dist[i][j]
		}
		q = q[1:]
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			t := dist[i][j]
			if k != d[matrix[i][j]] {
				t++
			}
			if x >= 0 && x < m && y >= 0 && y < n && t < dist[x][y] {
				dist[x][y] = t
				if dist[x][y] == dist[i][j] {
					q = append([][2]int{[2]int{x, y}}, q...)
				} else {
					q = append(q, [2]int{x, y})
				}
			}
		}
	}
}

TypeScript

function conveyorBelt(matrix: string[], start: number[], end: number[]): number {
    const dirs = [-1, 0, 1, 0, -1];
    const d: Map<string, number> = new Map();
    d.set('^', 0);
    d.set('>', 1);
    d.set('v', 2);
    d.set('<', 3);
    const q: number[][] = [start];
    const m = matrix.length;
    const n = matrix[0].length;
    const dist: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(1 << 30));
    dist[start[0]][start[1]] = 0;
    while (true) {
        const [i, j] = q.shift()!;
        if (i === end[0] && j === end[1]) {
            return dist[i][j];
        }
        for (let k = 0; k < 4; ++k) {
            const x = i + dirs[k];
            const y = j + dirs[k + 1];
            const t = dist[i][j] + (d.get(matrix[i][j]) === k ? 0 : 1);
            if (x >= 0 && x < m && y >= 0 && y < n && t < dist[x][y]) {
                dist[x][y] = t;
                if (t == dist[i][j]) {
                    q.unshift([x, y]);
                } else {
                    q.push([x, y]);
                }
            }
        }
    }
}

...