Python | Dynamic Programming | Breadth-First Search & Memoization
\n# Code\npython3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get grid dimensions\n        m, n = len(grid), len(grid[
\n# Code\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get grid dimensions\n        m, n = len(grid), len(grid[0])\n        \n        # Directions for moves: right, diagonal up-right, diagonal down-right\n        directions = [(0, 1), (-1, 1), (1, 1)]\n        \n        # DP memoization table initialized to -1\n        dp = [[-1] * n for _ in range(m)]\n        \n        def bfs(row, col):\n            # If already computed, return the stored value\n            if dp[row][col] != -1:\n                return dp[row][col]\n            \n            queue = deque([(row, col, 0)])  # (row, col, moves)\n            max_reachable_moves = 0  # Track max moves from this starting cell\n            \n            while queue:\n                r, c, moves = queue.popleft()\n                max_reachable_moves = max(max_reachable_moves, moves)\n                \n                for dr, dc in directions:\n                    nr, nc = r + dr, c + dc\n                    # Check boundaries and conditions for moving\n                    if 0 <= nr < m and 0 <= nc < n:\n                        if grid[nr][nc] > grid[r][c]:\n                            if dp[nr][nc] == -1 or dp[nr][nc] < moves + 1:\n                                dp[nr][nc] = moves + 1  # Update dp with moves count\n                                queue.append((nr, nc, moves + 1))\n            \n            # Store max moves from this starting cell in dp table\n            dp[row][col] = max_reachable_moves\n            return max_reachable_moves\n        \n        # Start BFS from each cell in the first column and calculate maximum moves\n        max_moves_result = 0\n        for start_row in range(m):\n            max_moves_result = max(max_moves_result, bfs(start_row, 0))\n        \n        return max_moves_result\n```
['Python3']