class Solution {
private static final int[][] directions = new int[][]{
{ -1, 0 },
{ 0, -1 },
{ 1, 0 },
{ 0, 1 }
};
public boolean findSafeWalk(List<List<Integer>> grid, int health) {
int m = grid.size();
int n = grid.get(0).size();
int[][] arrGrid = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arrGrid[i][j] = grid.get(i).get(j);
}
}
int[][] safeGrid = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(safeGrid[i], Integer.MIN_VALUE);
}
safeGrid[0][0] = health - arrGrid[0][0];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{0, 0});
while (!queue.isEmpty()) {
int[] loc = queue.poll();
int cx = loc[0];
int cy = loc[1];
for (int[] direction : directions) {
int x = cx + direction[0];
int y = cy + direction[1];
if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
int diff = -arrGrid[x][y];
if (safeGrid[cx][cy] + diff > safeGrid[x][y]) {
safeGrid[x][y] = safeGrid[cx][cy] + diff;
if (safeGrid[x][y] > 0) {
queue.offer(new int[]{x, y});
}
}
}
}
return safeGrid[m - 1][n - 1] > 0;
}
}
最新回复 (2)
Lvvvv07-02 09:54
1楼
基本是标准bfs的简单题。
class Solution {
public:
bool findSafeWalk(vector<vector<int>>& grid, int health) {
int m = grid.size(),n = grid[0].size();
std::vector<std::vector<int>> st(m,std::vector<int>(n,0));
queue<int> q;
std::vector<int> dx = {-1,0,1,0},dy = {0,1,0,-1};
st[0][0] = health - grid[0][0];
if(st[0][0] > 0) {
q.push(0);
}
while(!q.empty()) {
auto id = q.front();
q.pop();
int x = id / n, y = id % n;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
if(st[x][y] - grid[nx][ny] > st[nx][ny]) {
q.push(nx * n + ny);
st[nx][ny] = st[x][y] - grid[nx][ny];
}
}
}
}
return st[m - 1][n - 1] > 0;
}
};
Infinity4B07-02 11:53
2楼
算术评级6 第 139 场双周赛 Q2 难度分1608
迷迷糊糊学了一下01 BFS，迷迷糊糊做完了，感觉似懂非懂
class Solution:
def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
dirs = [(-1,0),(0,-1),(1,0),(0,1)]
m, n = len(grid), len(grid[0])
queue = deque([(0, 0)])
visited = [[False]*n for _ in range(m)]
dist = [[inf]*n for _ in range(m)]
dist[0][0]=grid[0][0]
visited[0][0]=True
while queue:
cur_m, cur_n = queue.popleft()
for a, b in dirs:
next_m, next_n = cur_m+a, cur_n+b
if 0<=next_m<m and 0<=next_n<n and not visited[next_m][next_n] and dist[cur_m][cur_n]+grid[next_m][next_n]<dist[next_m][next_n]:
dist[next_m][next_n] = dist[cur_m][cur_n]+grid[next_m][next_n]
if grid[next_m][next_n]==0:
queue.appendleft((next_m,next_n))
else:
queue.append((next_m,next_n))
visited[next_m][next_n]=True
Lvvvv 07-02 09:541楼
Infinity4B 07-02 11:532楼