golang 解法, 执行用时: 556 ms, 内存消耗: 11.3 MB, 提交时间: 2023-09-26 07:55:00

/**
 * 使用一个二维数组visit记录走到该位置的最低更改次数，
 * 如果下次走到这里需要修改的次数已经超过之前走到这里最小的修改次数，则直接回溯就可以了
 */
func minCost(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	ans := m + n - 2
	visit := make([][]int, m)
	for i := 0; i < m; i++ {
		visit[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			visit[i][j] = m + n - 2
		}
	}
	directs := [4][3]int{{0, 1, 1}, {0, -1, 2}, {1, 0, 3}, {-1, 0, 4}}
	var dfs func(x, y, count int)
	dfs = func(x, y, count int) {
		if count >= visit[x][y] {
			return
		}
		if x == m-1 && y == n-1 {
			if count < ans {
				ans = count
			}
		}
		for _, direct := range directs {
			dx, dy := x+direct[0], y+direct[1]
			if dx >= 0 && dy >= 0 && dx < m && dy < n {
				if count < visit[x][y] {
					visit[x][y] = count
				}
				if grid[x][y] != direct[2] {
					dfs(dx, dy, count+1)
				} else {
					dfs(dx, dy, count)
				}
			}
		}
	}
	dfs(0, 0, 0)
	return ans
}

golang 解法, 执行用时: 32 ms, 内存消耗: 7 MB, 提交时间: 2023-09-26 07:54:19

var (
	dirs = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
)

const inf = 0x3f3f3f3f

type edge struct {
	x    int
	y    int
	time int
} // 定义边结构体，字段为到to节点，和到to的时间

// go 语言中，不提供有限队列数据结构，需要结合heap自己实现
type hp []edge

func (h hp) Len() int              { return len(h) }
func (h hp) Less(i, j int) bool    { return h[i].time < h[j].time }
func (h hp) Swap(i, j int)         { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{})   { *h = append(*h, v.(edge)) }
func (h *hp) Pop() (v interface{}) { a := *h; *h, v = a[:len(a)-1], a[len(a)-1]; return }

func minCost(heights [][]int) int {

	m := len(heights)
	n := len(heights[0])

	dist := make([][]int, m)
	for i := 0; i < m; i++ {
		dist[i] = make([]int, n)

		for j := 0; j < n; j++ {
			dist[i][j] = inf
		}
	}

	dist[0][0] = 0 // 关键

	h := &hp{}
	heap.Init(h)
	heap.Push(h, edge{0, 0, 0})

	for h.Len() > 0 {
		node := heap.Pop(h).(edge)
		x, y, d := node.x, node.y, node.time

		if dist[x][y] > d { // 0 肯定不可能大于 d，所以第一次一定不走这个
			continue
		}

		if x == m-1 && y == n-1 {
			return d
		}

		for i := 0; i < 4; i++ {
			nx, ny := x+dirs[i][0], y+dirs[i][1]

			if nx >= 0 && nx < m && ny >= 0 && ny < n {
				var g int
				if i+1 == heights[x][y] {
					g = 0
				} else {
					g = 1
				}

				nc := dist[x][y] + g
				if nc < dist[nx][ny] {
					dist[nx][ny] = nc
					heap.Push(h, edge{nx, ny, nc})
				}
			}
		}
	}

	return 0
}

java 解法, 执行用时: 25 ms, 内存消耗: 42.8 MB, 提交时间: 2023-09-26 07:53:38

class Solution {
    int[][] dirs = {{0, 0}, {0, 1},{0, -1}, {1, 0}, {-1, 0}};

    // Dijkstra解法
    public int minCost(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 初始化结果数组
        int[] dis = new int[m * n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[0] = 0;
        // 记录访问过的节点
        Set<Integer> vis = new HashSet<>();
        // 创建优先级队列(根据最小代价升序排列)
        Queue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        // 优先队列保存当前位置的下标和最小代价
        queue.offer(new int[]{0, 0, 0});
        // BFS
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int x = arr[0], y = arr[1];
            int oldPos = x * n + y;
            // 避免重复访问
            if (vis.contains(oldPos)) {
                continue;
            }
            vis.add(oldPos);
            // 向四周(右-左-下-上)扩散
            for (int i = 1; i <= 4; i++) {
                int nx = x + dirs[i][0], ny = y + dirs[i][1];
                // 下标越界继续寻找下一个位置
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int newPos = nx * n + ny;
                // 到达当前位置的代价(方向相同则代价为0否则为1)
                int newDis = dis[oldPos] + (grid[x][y] == i ? 0 : 1);
                // 新的代价小于此前的最小代价
                if (newDis < dis[newPos]) {
                    // 更新最小代价
                    dis[newPos] = newDis;
                    // 当前位置入队
                    queue.offer(new int[]{nx, ny, newDis});
                }
            }
        }
        // 返回到达终点的最小代价
        return dis[m * n - 1];
    }

    // 0-1 bfs
    public int minCost2(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 初始化
        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(dis[i], Integer.MAX_VALUE);
        dis[0][0] = 0;
        // 创建双端队列
        ArrayDeque<int[]> deque = new ArrayDeque<int[]>();
        deque.addLast(new int[]{0, 0});
        while (!deque.isEmpty()) {
            int[] arr = deque.pollFirst();
            int x = arr[0], y = arr[1];
            // 向四周扩散(右-左-下-上)
            for (int i = 1; i <= 4; i++) {
                // 计算新节点下标
                int nx = x + dirs[i][0], ny = y + dirs[i][1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                // 若当前节点的箭头方向和本次移动方向相同，则成本为0，否则成本为1
                int cost = grid[x][y] == i ? 0 : 1;
                if (dis[x][y] + cost < dis[nx][ny]) {
                    // 更新到达新节点的最低成本
                    dis[nx][ny] = dis[x][y] + cost;
                    // 若移动方向相同，新节点重新加入队列头部，否则加入尾部
                    if (grid[x][y] == i) {
                        deque.addFirst(new int[]{nx, ny});
                    } else {
                        deque.addLast(new int[]{nx, ny});
                    }
                }
            }
        }
        return dis[m - 1][n - 1];
    }
}

python3 解法, 执行用时: 212 ms, 内存消耗: 18.4 MB, 提交时间: 2023-09-26 07:51:50

class Solution:
    # 0-1 bfs
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        BIG = int(1e9)
        dist = [0] + [BIG] * (m * n - 1)
        seen = set()
        q = collections.deque([(0, 0)])

        while len(q) > 0:
            x, y = q.popleft()
            if (x, y) in seen:
                continue
            seen.add((x, y))
            cur_pos = x * n + y
            for i, (nx, ny) in enumerate([(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]):
                new_pos = nx * n + ny
                new_dis = dist[cur_pos] + (1 if grid[x][y] != i + 1 else 0)
                if 0 <= nx < m and 0 <= ny < n and new_dis < dist[new_pos]:
                    dist[new_pos] = new_dis
                    if grid[x][y] == i + 1:
                        q.appendleft((nx, ny))
                    else:
                        q.append((nx, ny))
        
        return dist[m * n - 1]

    # Dijkstra 算法
    def minCost2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        BIG = int(1e9)
        dist = [0] + [BIG] * (m * n - 1)
        seen = set()
        q = [(0, 0, 0)]

        while len(q) > 0:
            cur_dis, x, y = heapq.heappop(q)
            if (x, y) in seen:
                continue
            seen.add((x, y))
            cur_pos = x * n + y
            for i, (nx, ny) in enumerate([(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]):
                new_pos = nx * n + ny
                new_dis = dist[cur_pos] + (1 if grid[x][y] != i + 1 else 0)
                if 0 <= nx < m and 0 <= ny < n and new_dis < dist[new_pos]:
                    dist[new_pos] = new_dis
                    heapq.heappush(q, (new_dis, nx, ny))
        
        return dist[m * n - 1]

cpp 解法, 执行用时: 48 ms, 内存消耗: 13.4 MB, 提交时间: 2023-09-26 07:50:42

using PII = pair<int, int>;

class Solution {
private:
    static constexpr int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    // Dijkstra 算法
    int minCost(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dist(m * n, INT_MAX);
        vector<int> seen(m * n, 0);
        dist[0] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> q;
        q.emplace(0, 0);
        
        while (!q.empty()) {
            auto [cur_dis, cur_pos] = q.top();
            q.pop();
            if (seen[cur_pos]) {
                continue;
            }
            seen[cur_pos] = 1;
            int x = cur_pos / n;
            int y = cur_pos % n;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                int new_pos = nx * n + ny;
                int new_dis = cur_dis + (grid[x][y] != i + 1);
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && new_dis < dist[new_pos]) {
                    dist[new_pos] = new_dis;
                    q.emplace(new_dis, new_pos);
                }
            }
        }

        return dist[m * n - 1];
    }
    
    // 0-1 广度优先搜索
    int minCost2(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dist(m * n, INT_MAX);
        vector<int> seen(m * n, 0);
        dist[0] = 0;
        deque<int> q;
        q.push_back(0);
        
        while (!q.empty()) {
            auto cur_pos = q.front();
            q.pop_front();
            if (seen[cur_pos]) {
                continue;
            }
            seen[cur_pos] = 1;
            int x = cur_pos / n;
            int y = cur_pos % n;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                int new_pos = nx * n + ny;
                int new_dis = dist[cur_pos] + (grid[x][y] != i + 1);
                
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && new_dis < dist[new_pos]) {
                    dist[new_pos] = new_dis;
                    if (grid[x][y] == i + 1) {
                        q.push_front(new_pos);
                    }
                    else {
                        q.push_back(new_pos);
                    }
                }
            }
        }

        return dist[m * n - 1];
    }
};