Beats 100%🔥|| DP🔥|| BFS🔥|| JAVA✅
Top-Down DP\n\nclass Solution {\n    int n,m;\n    Integer[][] memo;\n    public int maxMoves(int[][] grid) {\n        int ans=0;\n        n=grid.length;m=grid[
# Top-Down DP\n```\nclass Solution {\n    int n,m;\n    Integer[][] memo;\n    public int maxMoves(int[][] grid) {\n        int ans=0;\n        n=grid.length;m=grid[0].length;\n        memo=new Integer[n][m];\n        for(int i=0;i<n;i++){\n            ans=Math.max(ans,sol(grid,i,0));\n        }\n        return ans;\n    }\n    public int sol(int[][] grid,int r,int c){\n        if(c==m-1) return 0;\n        if(memo[r][c]!=null) return memo[r][c];\n        int ans=0;\n        if(grid[r][c]<grid[r][c+1]){\n            ans=Math.max(ans,sol(grid,r,c+1)+1);\n        }\n        if(r>0 && grid[r][c]<grid[r-1][c+1]){\n            ans=Math.max(ans,sol(grid,r-1,c+1)+1);\n        }\n        if(r<n-1 && grid[r][c]<grid[r+1][c+1]){\n            ans=Math.max(ans,sol(grid,r+1,c+1)+1);\n        }\n        return memo[r][c]=ans;\n    }\n}\n```\n# BFS\n```\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int ans=-1,n=grid.length,m=grid[0].length;\n        Queue<Pair> q=new LinkedList<>();\n        boolean[][] vis=new boolean[n][m];\n        for(int i=0;i<n;i++){\n            q.add(new Pair(i,0));\n            vis[i][0]=true;\n        }\n        int[] dir={0,1,-1};\n        while(!q.isEmpty()){\n            int size=q.size();\n            while(size-->0){\n                Pair x=q.poll();\n                for(int i:dir){\n                    int r=x.r+i,c=x.c+1;\n                    if(r>=0 && r<n && c<m && !vis[r][c] && grid[x.r][x.c]<grid[r][c]){\n                        vis[r][c]=true;\n                        q.add(new Pair(r,c));\n                    }\n                }\n            }\n            ans++;\n        }\n        return ans;\n    }\n}\nclass Pair{\n    int r,c;\n    Pair(int r,int c){\n        this.r=r;\n        this.c=c;\n    }\n}\n```
['Dynamic Programming', 'Breadth-First Search', 'Java']