Tableau Onsite Round 4 - DFS Dungeon

mail@pastecode.io avatar
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) {
        
    }


}