174. Dungeon Game
Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу.
У рыцаря есть начальное количество очков здоровья, представленное положительным целым numberм. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт.
Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами).
Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.
return минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу.
Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую Đầu vàoит рыцарь, и последнюю комнату, где заточена принцесса.
Ví dụ:
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
C# lời giải
đã khớp/gốcpublic class Solution {
const int inf = int.MaxValue;
int[,] dp;
int rows, cols;
public int GetMinHealth(int currCell, int nextRow, int nextCol) {
if (nextRow >= this.rows || nextCol >= this.cols)
return inf;
int nextCell = this.dp[nextRow, nextCol];
return Math.Max(1, nextCell - currCell);
}
public int CalculateMinimumHP(int[][] dungeon) {
this.rows = dungeon.Length;
this.cols = dungeon[0].Length;
this.dp = new int[rows, cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dp[i, j] = inf;
}
}
int currCell, rightHealth, downHealth, nextHealth, minHealth;
for (int row = this.rows - 1; row >= 0; --row) {
for (int col = this.cols - 1; col >= 0; --col) {
currCell = dungeon[row][col];
rightHealth = GetMinHealth(currCell, row, col + 1);
downHealth = GetMinHealth(currCell, row + 1, col);
nextHealth = Math.Min(rightHealth, downHealth);
if (nextHealth != inf) {
minHealth = nextHealth;
} else {
minHealth = currCell >= 0 ? 1 : 1 - currCell;
}
this.dp[row, col] = minHealth;
}
}
return this.dp[0, 0];
}
}C++ lời giải
bản nháp tự động, xem lại trước khi gửi#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
const int inf = int.MaxValue;
int[,] dp;
int rows, cols;
public int GetMinHealth(int currCell, int nextRow, int nextCol) {
if (nextRow >= this.rows || nextCol >= this.cols)
return inf;
int nextCell = this.dp[nextRow, nextCol];
return max(1, nextCell - currCell);
}
public int CalculateMinimumHP(int[][] dungeon) {
this.rows = dungeon.size();
this.cols = dungeon[0].size();
this.dp = new int[rows, cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
dp[i, j] = inf;
}
}
int currCell, rightHealth, downHealth, nextHealth, minHealth;
for (int row = this.rows - 1; row >= 0; --row) {
for (int col = this.cols - 1; col >= 0; --col) {
currCell = dungeon[row][col];
rightHealth = GetMinHealth(currCell, row, col + 1);
downHealth = GetMinHealth(currCell, row + 1, col);
nextHealth = min(rightHealth, downHealth);
if (nextHealth != inf) {
minHealth = nextHealth;
} else {
minHealth = currCell >= 0 ? 1 : 1 - currCell;
}
this.dp[row, col] = minHealth;
}
}
return this.dp[0, 0];
}
}Java lời giải
đã khớp/gốcclass MyCircularQueue {
private int[] queue;
private int capacity;
private int tailIndex = 0;
public MyCircularQueue(int capacity) {
this.capacity = capacity;
this.queue = new int[capacity];
}
public void enQueue(int value) {
queue[tailIndex] = value;
tailIndex = (tailIndex + 1) % capacity;
}
public int get(int index) {
return queue[index % capacity];
}
}
class Solution {
int inf = Integer.MAX_VALUE;
public int calculateMinimumHP(int[][] dungeon) {
int rows = dungeon.length, cols = dungeon[0].length;
MyCircularQueue dp = new MyCircularQueue(cols);
int minHealth, nextHealth, rightHealth, downHealth;
for (int row = rows - 1; row >= 0; row--) {
for (int col = cols - 1; col >= 0; col--) {
int currCell = dungeon[row][col];
if (col == cols - 1 && row == rows - 1) {
dp.enQueue(Math.max(1, 1 - currCell));
continue;
}
rightHealth = col == cols - 1 ? inf : Math.max(1, dp.get(col + 1) - currCell);
downHealth = row == rows - 1 ? inf : Math.max(1, dp.get(col) - currCell);
nextHealth = Math.min(rightHealth, downHealth);
minHealth = nextHealth == inf ? 1 : nextHealth;
dp.enQueue(minHealth);
}
}
return dp.get(0);
}
}JavaScript lời giải
đã khớp/gốcvar calculateMinimumHP = function (dungeon) {
let rows = dungeon.length,
cols = dungeon[0].length;
let dp = Array(rows)
.fill()
.map(() => Array(cols).fill(Number.MAX_SAFE_INTEGER));
const get_min_health = (currCell, nextRow, nextCol) => {
if (nextRow >= rows || nextCol >= cols) {
return Number.MAX_SAFE_INTEGER;
}
let nextCell = dp[nextRow][nextCol];
return Math.max(1, nextCell - currCell);
};
for (let row = rows - 1; row >= 0; --row) {
for (let col = cols - 1; col >= 0; --col) {
let currCell = dungeon[row][col];
let right_health = get_min_health(currCell, row, col + 1);
let down_health = get_min_health(currCell, row + 1, col);
let next_health = Math.min(right_health, down_health);
let min_health;
if (next_health !== Number.MAX_SAFE_INTEGER) {
min_health = next_health;
} else {
min_health = currCell >= 0 ? 1 : 1 - currCell;
}
dp[row][col] = min_health;
}
}
return dp[0][0];
};Python lời giải
đã khớp/gốcclass Solution(object):
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
rows, cols = len(dungeon), len(dungeon[0])
dp = [[float("inf")] * cols for _ in range(rows)]
def get_min_health(currCell: int, nextRow: int, nextCol: int) -> float:
if nextRow >= rows or nextCol >= cols:
return float("inf")
nextCell = dp[nextRow][nextCol]
# hero needs at least 1 point to survive
return max(1, nextCell - currCell)
for row in reversed(range(rows)):
for col in reversed(range(cols)):
currCell = dungeon[row][col]
right_health = get_min_health(currCell, row, col + 1)
down_health = get_min_health(currCell, row + 1, col)
next_health = min(right_health, down_health)
if next_health != float("inf"):
min_health = next_health
else:
min_health = 1 if currCell >= 0 else (1 - currCell)
dp[row][col] = min_health
return dp[0][0]Go lời giải
đã khớp/gốcfunc calculateMinimumHP(dungeon [][]int) int {
rows, cols := len(dungeon), len(dungeon[0])
dp := make([][]int, rows)
for i := 0; i < rows; i++ {
dp[i] = make([]int, cols)
for j := 0; j < cols; j++ {
dp[i][j] = 1<<31 - 1
}
}
get_min_health := func(currCell int, nextRow int, nextCol int) int {
if nextRow >= rows || nextCol >= cols {
return 1<<31 - 1
}
nextCell := dp[nextRow][nextCol]
return max(1, nextCell-currCell)
}
for row := rows - 1; row >= 0; row-- {
for col := cols - 1; col >= 0; col-- {
currCell := dungeon[row][col]
right_health := get_min_health(currCell, row, col+1)
down_health := get_min_health(currCell, row+1, col)
next_health := min(right_health, down_health)
min_health := 0
if next_health != 1<<31-1 {
min_health = next_health
} else {
if currCell >= 0 {
min_health = 1
} else {
min_health = 1 - currCell
}
}
dp[row][col] = min_health
}
}
return dp[0][0]
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}Algorithm
1️⃣
Определяем матрицу dp[row][col], где element dp[row][col] указывает минимальное количество очков здоровья, которое поit is required рыцарю, начиная с соответствующей ячейки подземелья dungeon[row][col], чтобы добраться до цели.
2️⃣
Для расчета значений матрицы dp начинаем с правого нижнего угла подземелья и идем в порядке справа-налево и снизу-вверх. Для каждой ячейки подземелья рассчитываем соответствующее значение dp[row][col].
3️⃣
Значение dp[row][col] определяется следующими условиями:
Если возможно, сделав шаг вправо из текущей ячейки подземелья, рыцарь может нуждаться в right_health очках здоровья.
Если возможно, сделав шаг вниз из текущей ячейки подземелья, рыцарь может нуждаться в down_health очках здоровья.
Если существует хотя бы одна из вышеуказанных альтернатив, берём минимальное значение из них для dp[row][col].
Если ни одна из вышеуказанных альтернатив не существует, то есть мы находимся в целевой ячейке, возможны два случая:
Если текущая ячейка содержит магический шар, то достаточно одного очка здоровья.
Если текущая ячейка содержит демона, то рыцарь должен иметь одно очко здоровья плюс очки урона, которые нанесет демон.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.