Shadecorps | Time: O(rows x cols) | Space: O(rows x cols) | Java
\n\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s a naive thinking, I can start from any position in the first column - so 
\n![image.png](https://assets.leetcode.com/users/images/0ac399c5-d868-44cf-88b7-5de70052285d_1730218507.544037.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s a naive thinking, I can start from any position in the first column - so I need to check from second column to last column where each cell in the column `grid[i][j]` can be accessed by `grid[i-1][j-1]`, `grid[i][j-1]` and `grid[i+1][j-1]`. \n\nThere is an exception \nFor first row which is accessed by `grid[i][j-1]`, `grid[i+1][j-1]` \ni.e., (`grid[0][j-1]`, `grid[1][j-1]` as `i=0` for first row) \n\nAnd last row which can be accessed by `grid[i-1][j-1]`, `grid[i][j-1]` \ni.e., (`grid[rows-2][i]`, `grid[rows-1][i]`)\n\nwhere `rows` is number of rows in the grid.\n\nConstruct a `dp[][]` as same dimensions as `grid[][]`.\n\nAll the previous column cell can access `second column`.  Hence, every cell values in `first column` are setted to `1` in the `dp[][]`\n\nTherefore, while iterating from `second column` to `last column`, if a cell  is accessible by previous column cells and the cell value is greater than previous column accessible cell values - then I will mark the cell as accessible in the `dp[][]`.\n\n# Complexity\n- Time complexity: $$O(m.n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: $$O(m.n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nwhere `m = number of rows` and `n = number of columns`\n\n# Code\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int row = grid.length, col = grid[0].length;\n        int[][] dp = new int[row][col];\n        int i=0;\n        for(i=0;i<row;i++) dp[i][0] = 1;\n        for(i=1;i<col;i++){\n            boolean flag = false;\n            // first row check\n            if(\n                (dp[0][i-1]>=1 && grid[0][i-1]<grid[0][i]) || \n                (dp[1][i-1]>=1 && grid[1][i-1]<grid[0][i]) \n            ){\n                flag = true;\n                dp[0][i]=i;\n            }\n            \n            // row (1) to row (n-2) check\n            for(int j=1;j<row-1;j++){\n                if(\n                    (dp[j-1][i-1]>=1 && grid[j-1][i-1]<grid[j][i]) || \n                    (dp[j][i-1]>=1 && grid[j][i-1]<grid[j][i]) || \n                    (dp[j+1][i-1]>=1 && grid[j+1][i-1]<grid[j][i]) \n                ){\n                    flag = true;\n                    dp[j][i]=i;\n                }\n            }\n\n            // last row check\n            if(\n                (dp[row-1][i-1]>=1 && grid[row-1][i-1]<grid[row-1][i]) || \n                (dp[row-2][i-1]>=1 && grid[row-2][i-1]<grid[row-1][i]) \n            ){\n                flag = true;\n                dp[row-1][i]=i;\n            }\n\n            if(!flag) return i-1;\n        }\n\n        return i-1;\n    }\n}\n```
['Java']