python3 解法, 执行用时: 84 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-25 10:33:33

d = {"^": (-1, 0),"v": (1, 0),"<": (0, -1),">": (0, 1)}
class Solution:
    def conveyorBelt(self, matrix: List[str], start: List[int], end: List[int]) -> int:
        m, n = len(matrix), len(matrix[0])
        q = deque([(0, start[0], start[1])])
        book = [[1234567890123] * n for _ in range(m)]
        book[start[0]][start[1]] = 0
        while q:
            t, x, y = q.popleft()
            if [x, y] == end: return t
            for dr, (dx, dy) in d.items():
                nx, ny = x + dx, y + dy
                if not (0 <= nx < m and 0 <= ny < n): continue
                nt = t + int(dr != matrix[x][y])
                if dr == matrix[x][y]:
                    if book[nx][ny] <= t: continue
                    book[nx][ny] = t
                    q.appendleft((t, nx, ny))
                else:
                    if book[nx][ny] <= t + 1: continue
                    book[nx][ny] = t + 1
                    q.append((t + 1, nx, ny))

java 解法, 执行用时: 15 ms, 内存消耗: 42.1 MB, 提交时间: 2023-10-25 10:31:26

class Solution {
    
    private int ans;
    private int[][] dis;
    private int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public void spfa(int[] start, int[] end, int m, int n, char[][] map, int cnt){
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        dis[start[0]][start[1]] = 0;
        while (!q.isEmpty()){
            int[] cur = q.poll();
            for (int i = 0; i < 4; ++i){
                int x = cur[0] + dir[i][0], y = cur[1] + dir[i][1];
                if (x >= 0 && x < m && y >= 0 && y < n){
                    int len = 1;
                    if ((i == 0 && map[cur[0]][cur[1]] == '^')
                            || (i == 1 && map[cur[0]][cur[1]] == 'v')
                            || (i == 2 && map[cur[0]][cur[1]] == '<')
                            || (i == 3 && map[cur[0]][cur[1]] == '>')){
                        len = 0;
                    }
                    if (dis[cur[0]][cur[1]] + len < dis[x][y]){
                        dis[x][y] = dis[cur[0]][cur[1]] + len;
                        q.offer(new int[]{x, y});
                    }
                }
            }
        }
    }

    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        int m = matrix.length, n = matrix[0].length();
        char[][] map = new char[m][n];
        for (int i = 0; i < m; ++i){
            map[i] = matrix[i].toCharArray();
        }
        dis = new int[m][n];
        for (int i = 0; i < m; ++i){
            for (int j = 0; j < n; ++j){
                dis[i][j] = 1000000;
            }
        }
        ans = Integer.MAX_VALUE;
        spfa(start, end, m, n, map, 0);
        return dis[end[0]][end[1]];
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 9.3 MB, 提交时间: 2023-10-25 10:30:53

class Solution {
public:
    typedef pair<int, int> PII;
    int dist[110][110]; //需要更改传送带的次数。
    bool st[110][110];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //4个方向。上右下左。
    char g[4] = {'^', '>', 'v', '<'};
    
    int conveyorBelt(vector<string>& matrix, vector<int>& start, vector<int>& end) {
        int n = matrix.size(), m = matrix[0].size();
        
        deque<PII> q;
        
        q.push_back({start[0], start[1]});
        memset(dist, -1, sizeof dist);
        dist[start[0]][start[1]] = 0;
        
        while (q.size())
        {
            auto t = q.front();
            q.pop_front();
            
            int x = t.first, y = t.second;
            //到终点，直接return
            if (x == end[0]  && y == end[1]) return dist[x][y];
            if (st[x][y]) continue;
            st[x][y] = true;
            
            //printf("x = %d, y = %d, dist = %d\n", x, y, dist[x][y]);
            for (int i = 0; i < 4; i ++ )
            {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
                
                if (g[i] == matrix[x][y]) //如果当前前进的方向 和传送带一个方向 加入队头
                {
                    q.push_front({a, b});
                    dist[a][b] = dist[x][y];
                }
                else //前进方向和传送带不是一个方向，加入队尾。
                {
                    q.push_back({a, b});
                    //如果当前点被更新过, 则更新为最小值。
                    if (dist[a][b] != -1) dist[a][b] = min(dist[a][b], dist[x][y] + 1);
                    else dist[a][b] = dist[x][y] + 1;
                }
                //cout << a << ' ' << b << ' ' << dist[a][b] << endl;
            }
        }
        return 0;
    }
};