Got MLE in extreme large test cases, is there anyone can help to solve the problem in dfs


  • 0
    S

    '''
    public class Solution {
    int small,big;
    boolean [][]visited;
    public boolean canMeasureWater(int x, int y, int z) {
    if(x>y)return canMeasureWater(y,x,z);
    if(z>x+y)return false;
    small=x;
    big=y;
    visited=new boolean[x+1][y+1];
    boolean [][]visited=new boolean[x+1][y+1];
    return helper(x,0,z);
    }
    public boolean helper(int x,int y,int z){
    if(x+y==z){
    return true;
    }
    if(x==small&&y==big)return false;
    if(x==0&&y==0)return false;
    visited[x][y]=true;

        boolean ans1,ans2,ans3,ans4,ans5,ans6;
        if(x==0||y==big||visited[x+y-(Math.min(big,x+y))][Math.min(big,x+y)])ans1=false;
        else ans1=helper(x+y-(Math.min(big,x+y)),Math.min(big,x+y),z); // pour x-->y
        if(y==0||x==small||visited[Math.min(small,x+y)][x+y-Math.min(small,x+y)]) ans2=false;
        else ans2=helper(Math.min(small,x+y),x+y-Math.min(small,x+y),z); //pour y-->x
        if(x==small||visited[small][y])ans3=false;
        else ans3=helper(small,y,z); 
        if(y==big||visited[x][big])ans4=false;
        else ans4=helper(x,big,z);
        if(x==0||visited[0][y])ans5=false;
        else ans5=helper(0,y,z);
        if(y==0||visited[x][0])ans6=false;
        else ans6=helper(x,0,z);
        return ans1||ans2||ans3||ans4||ans5||ans6;
    }
    

    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.