Writer: Steven, Lee
Date: 1/18, Friday
Purpose: Solving #174 Dungeon Game
Level: Hard
Percentage: 26.1% have solved this problem
Time: it took me 7 hours :)
Time Complexity: O(n^2) worst case
Dynamic programming * reference * => https://www.youtube.com/watch?v=vYquumk4nWw
한국어 버전은 밑에 있습니다.
* Caution * Before you read the solution that I used, you need to solve this problem by yourself
* Description *
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.
Note:
- The knight's health has no upper bound.
- Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path.RIGHT-> RIGHT -> DOWN -> DOWN
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
* What is the Idea? *
I can solve the problem by making map consisted of HP and considering a few conditions. and I calculated hp points from the last to first. By the way, Here are rules I needed to pay attention.
1. If the integer in the position is bigger than -1 (int >= 0) then, HP should be 1.
2. If the integer in the position is smaller than 0 (int < 0) then, HP should be -int + 1.
3. The knight has to move smaller integer between right and down.
I would like to explain more details with certain example. Given dungeon looks like this.
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
1. We have to make the hp map (4 X 4) which is bigger than the given dungeon. Why? It's obvious that we are going to compare the Integers of right and down every time. so that means we are also going to compare the edge of the dungeon. Then, the map looks like this.
X X X MAX
X X X MAX
X X X MAX
Max Max Max MAX
2. I already told you that there are three rules we have to keep in mind. Let's set the first hp in this case.
The last number -5 is smaller than 0, HP should be 6 (-(-5) + 1). Here is the map.
X X X MAX
X X X MAX
X X 6 MAX
Max Max Max MAX
3. We should remember the last rule "the knight has to move lower integer between right and down". the number next to the last integer (6) is 30. we can know what the number is smaller by looking at right and down at the position. In this case, the group is (6, Max). It is quite easy to notice the knight should go right. Then, how can we get HP? It's not a big deal just subtracting the number where the knight going to move to the number where the knight is. If the result is smaller than 0, it should be 1. In this case, 6 - 30 => -23 so it should be 1.
Let's keep do this. the number next to the Integer (30) is 10. the right and down at the position are (1, Max). so knight has to move right. we can get HP simply. Subtracting the number where the knight going to move to the number where the knight is. If the result is smaller than 0, It should be 1. In this case, 1 - 10 = > -9 so it should be 1.
Let's keep do this process. the next number is 1. the right and down at the position are (Max, 6). so knight has to move down. we can get HP simply. Subtracting the number where the knight going to move to the number where the knight is. If the result is smaller than 0, It should be 1. In this case, 6 - 1 => 5 so It should be 5.
If we gonna do the same thing again, the map looks like this.
7 5 2 MAX
6 11 5 MAX
1 1 6 MAX
Max Max Max MAX
5. Clear :)
* Check *
you can check out your answer on this site.
https://leetcode.com/problems/dungeon-game/
(한국어)
* 주의 * 솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.
* 지문 *
어떤 악마가 공주 (P)를 납치하고 그녀를 던전 오른쪽 맨 밑에 감금을 했습니다. 던전은 M x N개의 방으로 구성된 2D 격자판입니다. 왼쪽 맨 위에 맨 처음 배치되어 있는 우리의 씩씩한 용사 (K)는 공주를 구하기 위해 던전을 통해서 꼭 싸워야 합니다. 용사님은 양의 정수로 되어 있는 초기 에너지를 지니고 있습니다. 만약 어떤 지점에서 에너지가 0이나 더 떨어지게 되면 그는 즉시 죽게됩니다..
어떤 방에는 악마들이 지키고 있기 때문에 용사님이 그 방에 들어가면 에너지를 그 방의 음의 정수만큼 잃게 됩니다. 또 어떤 방은 빈 방이 있습니다 (0's). 또는 용사님의 에너지를 증가시켜주는 마법 구슬이 있는 방이 있습니다.(양의 정수)
공주를 최대한 빨리 구출하기 위해서 용사님은 오른쪽 또는 밑으로 차례대로 움직이기로 결심했습니다.
공주를 구출할 수 있게 용사님의 초기 에너지를 결정하는 함수를 작성하세요 !!
노트:
* 용사님의 에너지는 상한값이 없습니다.
* 어떤 방에든지 몬스터 방 또는 마법 구슬 방이 있을 수 있습니다. 심지어 용사가 시작되는 방, 공주가 갇혀 있는 방조차도 이 규칙이 적용 됩니다.
예를 들어, 밑에 주어진 던전에서 용사님의 초기 에너지는 적어도 7이어야 합니다. 왜냐하면 오른쪽 -> 오른쪽 -> 밑 -> 밑이 가장 최적화 된 길이기 때문이죠 ^^
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
* 아이디어 *
저는 HP로 구성된 맵을 만들고 몇 개의 조건을 고려해서 이 문제를 풀었습니다. 그리고 hp 포인트를 구할 때 첫 번째에서 마지막으로 가는 것이 아닌 마지막에서 첫 번째 순서로 했습니다. 여기 제가 주의 깊게 봐야 했던 규칙들입니다.
1. 만약 위치에 있는 숫자가 -1보다 크면 (int >= 0) HP는 1입니다.
2. 만약 위치에 있는 숫자가 0보다 작으면 (int < 0) HP는 -int + 1입니다.
3. 용사님는 오른쪽과 밑 사이에서 더 작은 쪽으로 움직여야 합니다.
특정 예시와 함께 더 자세히 설명하겠습니다. 주어진 던전은 이렇게 생겼습니다.
| -2 (K) | -3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
1. HP 맵(4 X 4)을 만들 때 주어진 던전보다 더 커야 합니다. 왜냐고요?? 명백히 우리들은 오른쪽과 밑의 숫자들을 매번 비교할 것입니다. 그말은 즉슨 던전의 가장자리 또한 비교할 것입니다. 맵은 이렇게 생겼습니다.
X X X MAX
X X X MAX
X X X MAX
Max Max Max MAX
2. 여러분께 말했던 것처럼 우리들이 명심해야 할 세 가지 규칙이 있습니다. 이 부분에서 가장 처음 HP를 셋팅을 해봅시다.
마지막 숫자 -5는 0보다 작습니다. 따라서 HP는 6 (-(-5) +1)이 되어야 합니다. 다음 맵입니다.
X X X MAX
X X X MAX
X X 6 MAX
Max Max Max MAX
3. 우리들은 맨 마지막 규칙인 용사님는 오른쪽과 밑 사이에서 더 작은 쪽으로 움직여야 합니다라는 것을 잘 기억해야 합니다. 마지막 정수 (6)의 다음 숫자는 30입니다. 우리들은 어떤 숫자가 더 작은지 그 위치에서 오른쪽과 밑 부분을 보면 알 수 있습니다. 이 예시에서 그 그룹은 (6, Max)입니다. 용사님이 오른쪽으로 가야 한다는 것을 쉽게 알 수 있습니다. 그러면 어떻게 HP를 얻을 수 있을까요?? 그것은 그렇게 어렵지 않습니다. 용사님이 가야할 부분에서 용사님이 있는 부분을 뺴기만 하면 됩니다 만약 결과가 0보다 작을 때 그것은 1입니다. 이 부분에서 6 - 30 => -23 그래서 1입니다.
계속 해봅시다. 30의 다음 숫자는 10입니다. 그 위치에서 오른쪽과 아랫쪽은 (1, Max)입니다. 그래서 용사님은 오른쪽으로 갑니다. 우리는 쉽게 HP를 구할 수 있습니다. 용사님이 가야할 부분에서 용사님이 있는 부분을 빼면 됩니다. 만약 결과가 0보다 작을 때 그것은 1입니다. 이 부분에서 1 - 10 => -9입니다. 따라서 1입니다.
계속 이것을 해봅시다. 다음 숫자는 1입니다. 그 위치에서 오른쪽과 아랫쪽은 (Max, 6) 그래서 용사는 밑으로 가야 합니다. 우리는 쉽게 HP를 구할 수 있습니다. 용사님이 가야할 부분에서 용사님이 있는 부분을 뺍니다 만약 결과가 0보다 작으면 그것은 1입니다. 이 부분에서 6 - 1 => 5 그렇기 때문에 5입니다.
이것을 계속 해보면 맵의 모습은 다음과 같습니다.
7 5 2 MAX
6 11 5 MAX
1 1 6 MAX
Max Max Max MAX
5. 완성 :)
* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.
Code & 코드
You need to read the code by yourself
스스로 코드를 읽을 줄 알아야 합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | public class DungeonGame_174 { public static int calculateMinimumHP(int[][] map) { int[][] dp = new int[map.length + 1][map[0].length + 1]; for (int i = 0; i < dp.length; i++) { dp[i][dp[0].length - 1] = Integer.MAX_VALUE; } for (int i = 0; i < dp[0].length; i++) { dp[dp.length - 1][i] = Integer.MAX_VALUE; } int dpRow = dp.length - 2; int dpCol = dp[0].length - 2; dp[dpRow][dpCol] = map[dpRow][dpCol] > 0 ? 1 : -map[dpRow][dpCol] + 1; for (int i = dpRow ; i >= 0; i--) { for (int j = dpCol ; j >= 0; j--) { if (i == dpRow && j == dpCol) continue; dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - map[i][j]); } } return dp[0][0]; } public static void main(String[] args) { int[][] dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}}; int result = calculateMinimumHP(dungeon); System.out.println("Result: " + result); } } | cs |
'DataStructures & Algorithm (Practice)' 카테고리의 다른 글
| Google #2 Number of Islands (0) | 2019.01.27 |
|---|---|
| Google #1 Longest Substring with At Most Two Distinct Characters (0) | 2019.01.24 |
| Leetcode #84 Largest Rectangle in Histogram (0) | 2019.01.02 |
| Leetcode #45 Jump Game II (0) | 2018.12.29 |
| Leetcode #51 N-Queens (0) | 2018.12.27 |
