✅[Python] Simple and Clean, beats 79.75%✅
Please upvote if you find this helpful. \u270C\n\n\nThis is an NFT\n\n\n# Intuition\nThe problem asks us to find the maximum number of moves that can be perform
### Please upvote if you find this helpful. \u270C\n<img src="https://assets.leetcode.com/users/images/b8e25620-d320-420a-ae09-94c7453bd033_1678818986.7001078.jpeg" alt="Cute Robot - Stable diffusion" width="200"/>\n\n*This is an NFT*\n\n\n# Intuition\nThe problem asks us to find the maximum number of moves that can be performed in a grid by starting at any cell in the first column and moving to cells that have strictly bigger values than the current cell. Our first thought might be to try all possible starting cells and find the maximum number of moves for each one. However, this approach would be inefficient as it would require us to traverse the entire grid for each starting cell.\n\n# Approach\nA more efficient approach would be to use `Depth First Search (DFS)` to traverse the grid and find the maximum number of moves for each starting cell. We can start at any cell in the `first column` and move to any of the cells: `(row - 1, col + 1), (row, col + 1) and (row + 1, col + 1)` such that the value of the cell we move to is `strictly bigger than the value of the current cell`. We can use a recursive function `dfs(i,j)` that takes as input the current cell `(i,j)` and returns the maximum number of moves that can be performed starting from this cell. We can use memoization to avoid recomputing the same subproblems multiple times.\n\nHere is an outline of our approach:\n\n1. Initialize `n`, `m`, and `dirs` with the dimensions of the grid and the possible directions of movement.\n\n1. Define a recursive function `dfs(i,j)` that takes as input the current cell `(i,j)` and returns the maximum number of moves that can be performed starting from this cell.\n\n1. Use a loop to iterate over all possible directions of movement.\n\n1. For each direction, compute the new cell (new_i,new_j) and check if it is within the bounds of the grid and if its value is strictly bigger than the value of the current cell.\n\n1. If these conditions are satisfied, update moves with the maximum value between its current value and `1+dfs(new_i,new_j)`.\n\n1. Return `moves`.\n\n1. Call `dfs(i,0)` for all cells in the first column and return their maximum value.\n\n\n\n# Complexity\n- Time complexity: $$O(m*n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        n, m, dirs = len(grid), len(grid[0]), [(0,1),(1,1),(-1,1)]\n        @cache\n        def dfs(i,j):\n            moves = 0\n            for x,y in dirs:\n                new_i, new_j = i+x, j+y\n                if 0<=new_i<n and new_j<m and grid[i][j]<grid[new_i][new_j]:\n                    moves = max(moves,1+dfs(new_i,new_j))\n            return moves\n        return max(dfs(i,0) for i in range(n))\n```
['Depth-First Search', 'Graph', 'Recursion', 'Matrix', 'Python3']