# Tableau Onsite Round 4 - DFS Dungeon

unknown
plain_text
2 years ago
2.3 kB
1
Indexable
Never
```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

// Start 1 health
//
public class Solution {
public static void main(String args[]) throws Exception {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
}

//O(m*n+(2^(m+n-1))

// public static int findMinimumHealth(int[][] room) {
//     int m = room.length, n = room[0].length;

//     // maxhealth = sum of all negative in room
//     // O(m*n)

//     int maxHealth = m*n*1000;
//     for (int i = 1; i <= maxHealth ; i++) {
//         boolean found = dfs(room, i, 0, 0);
//         if (found) {
//             return i;
//         }
//     };

//     return -1; // Should never reach
// }

// public static boolean dfs(int[][] room, int health, int x, int y) {
//     int m = room.length, n = room[0].length;
//     int currentHealth = health + room[x][y];
//     // out of bound / dead
//     if (x < m || y < n || health <= 0 || currentHealth <= 0) {
//         return false;
//     }

//     // We Won
//     if (x == m-1 && y == n-1) {
//         return true;
//     }

//     return dfs(room, currentHealth, x+1, y) || dfs(room, currentHealth, x, y+1);
// }
public static int findMinimumHealth(int[][] room) {
int m = room.length, n = room[0].length;

int min = dfs(room, i, 0, 0);
return -1; // Should never reach
}

public static int dfs(int[][] room, int health, int x, int y) {
int m = room.length, n = room[0].length;
int currentHealth = health + room[x][y];
// out of bound / dead
if (x < m || y < n || health <= 0 || currentHealth <= 0) {
return false;
}

// We Won
if (x == m-1 && y == n-1) {
return true;
}

return dfs(room, currentHealth, x+1, y) || dfs(room, currentHealth, x, y+1);
}
min 6
[2,2] 6
[2,1]

[2,1] 0
[1,2] 5 [1,2]6 = 5

...

[0,0] -

public static int dfs(int[][] room, int health, int x, int y, int[][] min) {

}

}```