Shopee 7.5 后端笔试 生命值
生命值 DFS 70%
import java.util.*;
public class Solution {
int[][] DIRS = new int[][] {
{0, 1}, {0, -1}, {1, 0}, {-1, 0}
};
boolean[][] visited;
int M, N;
int res;
public int minimumInitHealth(int[][] rooms, int[] startPoint, int[] endPoint) {
res = Integer.MIN_VALUE;
M = rooms.length;
N = rooms[0].length;
visited = new boolean[M][N];
dfs(rooms, startPoint[0], startPoint[1], endPoint[0], endPoint[1], 0, 0);
return -res + 1;
}
private void dfs(int[][] rooms, int i, int j, int x, int y, int health, int minHealth) {
health += rooms[i][j];
minHealth = Math.min(minHealth, health);
if (x == i && y == j) {
res = Math.max(res, minHealth);
return;
}
visited[i][j] = true;
for (int w = 0; w < 4; w++) {
int newI = i + DIRS[w][0];
int newJ = j + DIRS[w][1];
if (newI >= 0 && newI < M && newJ >= 0 && newJ < N && !visited[newI][newJ]) {
dfs(rooms, newI, newJ, x, y, health, minHealth);
}
}
visited[i][j] = false;
}
}
请大佬指教。
