穿越网格图的安全路径

3286. 穿越网格图的安全路径

给你一个 m x n 的二进制矩形 grid 和一个整数 health 表示你的健康值。

你开始于矩形的左上角 (0, 0) ，你的目标是矩形的右下角 (m - 1, n - 1) 。

你可以在矩形中往上下左右相邻格子移动，但前提是你的健康值始终是正数。

对于格子 (i, j) ，如果 grid[i][j] = 1 ，那么这个格子视为 不安全 的，会使你的健康值减少 1 。

如果你可以到达最终的格子，请你返回 true ，否则返回 false 。

注意，当你在最终格子的时候，你的健康值也必须为正数。

示例 1：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1

输出：true

解释：

沿着下图中灰色格子走，可以安全到达最终的格子。

示例 2：

输入：grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3

输出：false

解释：

健康值最少为 4 才能安全到达最后的格子。

示例 3：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5

输出：true

解释：

沿着下图中灰色格子走，可以安全到达最终的格子。

任何不经过格子 (1, 1) 的路径都是不安全的，因为你的健康值到达最终格子时，都会小于等于 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
2 <= m * n
1 <= health <= m + n
grid[i][j] 要么是 0 ，要么是 1 。

相似题目

网格中的最短路径

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool findSafeWalk(vector<vector<int>>& grid, int health) { } };

python3 解法, 执行用时: 51 ms, 内存消耗: 16.9 MB, 提交时间: 2024-10-20 10:12:12

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = grid[0][0]
        q = deque([(0, 0)])
        while True:
            i, j = q.popleft()
            if dis[i][j] >= health:
                return False
            if i == m - 1 and j == n - 1:
                return True
            for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
                if 0 <= x < m and 0 <= y < n:
                    cost = grid[x][y]
                    if dis[i][j] + cost < dis[x][y]:
                        dis[x][y] = dis[i][j] + cost
                        if cost == 0:
                            q.appendleft((x, y))
                        else:
                            q.append((x, y))

    def findSafeWalk2(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = grid[0][0]
        q = deque([(0, 0)])
        while q:
            i, j = q.popleft()
            for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
                if 0 <= x < m and 0 <= y < n:
                    cost = grid[x][y]
                    if dis[i][j] + cost < dis[x][y]:
                        dis[x][y] = dis[i][j] + cost
                        if cost == 0:
                            q.appendleft((x, y))
                        else:
                            q.append((x, y))
        return dis[-1][-1] < health

golang 解法, 执行用时: 3 ms, 内存消耗: 8.7 MB, 提交时间: 2024-10-20 10:11:33

func findSafeWalk(grid [][]int, health int) bool {
	type pair struct{ x, y int }
	dirs := []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
	m, n := len(grid), len(grid[0])
	dis := make([][]int, m)
	for i := range dis {
		dis[i] = make([]int, n)
		for j := range dis[i] {
			dis[i][j] = math.MaxInt
		}
	}

	dis[0][0] = grid[0][0]
	q := [2][]pair{{{}}} // 两个 slice 头对头来实现 deque
	for len(q[0]) > 0 || len(q[1]) > 0 {
		var p pair
		if len(q[0]) > 0 {
			p, q[0] = q[0][len(q[0])-1], q[0][:len(q[0])-1]
		} else {
			p, q[1] = q[1][0], q[1][1:]
		}
		i, j := p.x, p.y
		for _, d := range dirs {
			x, y := i+d.x, j+d.y
			if 0 <= x && x < m && 0 <= y && y < n {
				cost := grid[x][y]
				if dis[i][j]+cost < dis[x][y] {
					dis[x][y] = dis[i][j] + cost
					q[cost] = append(q[cost], pair{x, y})
				}
			}
		}
	}
	return dis[m-1][n-1] < health
}

func findSafeWalk2(grid [][]int, health int) bool {
	type pair struct{ x, y int }
	dirs := []pair{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
	m, n := len(grid), len(grid[0])
	dis := make([][]int, m)
	for i := range dis {
		dis[i] = make([]int, n)
		for j := range dis[i] {
			dis[i][j] = math.MaxInt
		}
	}

	dis[0][0] = grid[0][0]
	q := [2][]pair{{{}}} // 两个 slice 头对头来实现 deque
	for {
		var p pair
		if len(q[0]) > 0 {
			p, q[0] = q[0][len(q[0])-1], q[0][:len(q[0])-1]
		} else {
			p, q[1] = q[1][0], q[1][1:]
		}
		i, j := p.x, p.y
		if dis[i][j] >= health {
			return false
		}
		if i == m-1 && j == n-1 {
			return true
		}
		for _, d := range dirs {
			x, y := i+d.x, j+d.y
			if 0 <= x && x < m && 0 <= y && y < n {
				cost := grid[x][y]
				if dis[i][j]+cost < dis[x][y] {
					dis[x][y] = dis[i][j] + cost
					q[cost] = append(q[cost], pair{x, y})
				}
			}
		}
	}
}

java 解法, 执行用时: 6 ms, 内存消耗: 43.9 MB, 提交时间: 2024-10-20 10:10:59

class Solution {
    private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int m = grid.size();
        int n = grid.get(0).size();
        Object[][] a = new Object[m][];
        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            a[i] = grid.get(i).toArray();
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }

        dis[0][0] = (int) a[0][0];
        Deque<int[]> q = new ArrayDeque<>();
        q.addFirst(new int[]{0, 0});
        while (true) {
            int[] p = q.pollFirst();
            int i = p[0];
            int j = p[1];
            if (dis[i][j] >= health) {
                return false;
            }
            if (i == m - 1 && j == n - 1) {
                return true;
            }
            for (int[] d : DIRS) {
                int x = i + d[0];
                int y = j + d[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int cost = (int) a[x][y];
                    if (dis[i][j] + cost < dis[x][y]) {
                        dis[x][y] = dis[i][j] + cost;
                        if (cost == 0) {
                            q.addFirst(new int[]{x, y});
                        } else {
                            q.addLast(new int[]{x, y});
                        }
                    }
                }
            }
        }
    }

    public boolean findSafeWalk2(List<List<Integer>> grid, int health) {
        int m = grid.size();
        int n = grid.get(0).size();
        Object[][] a = new Object[m][];
        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            a[i] = grid.get(i).toArray();
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }

        dis[0][0] = (int) a[0][0];
        Deque<int[]> q = new ArrayDeque<>();
        q.addFirst(new int[]{0, 0});
        while (!q.isEmpty()) {
            int[] p = q.pollFirst();
            int i = p[0];
            int j = p[1];
            for (int[] d : DIRS) {
                int x = i + d[0];
                int y = j + d[1];
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int cost = (int) a[x][y];
                    if (dis[i][j] + cost < dis[x][y]) {
                        dis[x][y] = dis[i][j] + cost;
                        if (cost == 0) {
                            q.addFirst(new int[]{x, y});
                        } else {
                            q.addLast(new int[]{x, y});
                        }
                    }
                }
            }
        }
        return dis[m - 1][n - 1] < health;
    }
}

cpp 解法, 执行用时: 7 ms, 内存消耗: 31.4 MB, 提交时间: 2024-10-20 10:10:22

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        dis[0][0] = grid[0][0];
        deque<pair<int, int>> q;
        q.emplace_front(0, 0);
        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop_front();
            for (auto& [dx, dy] : DIRS) {
                int x = i + dx, y = j + dy;
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int cost = grid[x][y];
                    if (dis[i][j] + cost < dis[x][y]) {
                        dis[x][y] = dis[i][j] + cost;
                        cost == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y);
                    }
                }
            }
        }
        return dis[m - 1][n - 1] < health;
    }

    bool findSafeWalk2(vector<vector<int>>& grid, int health) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        dis[0][0] = grid[0][0];
        deque<pair<int, int>> q;
        q.emplace_front(0, 0);
        while (true) {
            auto [i, j] = q.front();
            q.pop_front();
            if (dis[i][j] >= health) {
                return false;
            }
            if (i == m - 1 && j == n - 1) {
                return true;
            }
            for (auto& [dx, dy] : DIRS) {
                int x = i + dx, y = j + dy;
                if (0 <= x && x < m && 0 <= y && y < n) {
                    int cost = grid[x][y];
                    if (dis[i][j] + cost < dis[x][y]) {
                        dis[x][y] = dis[i][j] + cost;
                        cost == 0 ? q.emplace_front(x, y) : q.emplace_back(x, y);
                    }
                }
            }
        }
    }
};

上一题

下一题

详情