Python | 4 Solutions | 1D/2D DP | DFS | BFS | Easy to understand
Intuition\nI have 4 solutions for this:\n\n1. 2-D Dynamic Programming Solution\n2. 1-D Dynamic Programming Solution\n2. Depth-First Search Solution\n3. Breath-F
# Intuition\nI have 4 solutions for this:\n\n1. 2-D Dynamic Programming Solution\n2. 1-D Dynamic Programming Solution\n2. Depth-First Search Solution\n3. Breath-First Search Solution\n\n# Complexity\n- Time complexity: $$O(m*n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m*n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# 2-D Dynamic Programming Solution\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the dimensions of the grid\n        m = len(grid)\n        n = len(grid[0])\n        \n        # Initialize the maximum operations to zero\n        maxOp = 0\n        \n        # Create a DP table initialized to zero\n        dp = [[0] * n for _ in range(m)]\n        \n        # Directions array to explore neighboring rows (up, same, down)\n        direction = [-1, 0, 1]\n        \n        # Iterate over each column\n        for j in range(n):\n            # Iterate over each row\n            for i in range(m):\n                # Check if current cell in dp table equals to the column index\n                if dp[i][j] == j:\n                    # Explore all three possible row movements\n                    for ni in direction:\n                        # Check boundaries and conditions to update dp table\n                        if 0 <= i + ni < m and 0 < j + 1 < n and grid[i + ni][j + 1] > grid[i][j] and dp[i][j] + 1 > dp[i + ni][j + 1]:\n                            # Update the dp table with the new maximum moves\n                            dp[i + ni][j + 1] = dp[i][j] + 1\n                            # Update the maxOp if the new value is greater\n                            if dp[i + ni][j + 1] > maxOp:\n                                maxOp = dp[i + ni][j + 1]\n                                # If maxOp reaches the last column, return it immediately\n                                if maxOp == n - 1:\n                                    return maxOp\n        # Return the maximum operations found\n        return maxOp\n```\n\n# 1-D Dynamic Programming Solution\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the number of rows and columns in the grid\n        m = len(grid)\n        n = len(grid[0])\n        \n        # Initialize the maximum number of valid moves to zero\n        maxOp = 0\n        \n        # Initialize the dp array to track the farthest column reached for each row\n        dp = [0] * m\n        \n        # Define possible directions for row movement (up, no movement, down)\n        direction = [-1, 0, 1]\n        \n        # Iterate over columns starting from the second one\n        for j in range(1, n):\n            # Create a copy of the dp array to update for the current column\n            dp2 = dp[:]\n            \n            # Iterate over each row\n            for i in range(m):\n                # Try all possible directions\n                for x in direction:\n                    newi = i + x  # Calculate the new row index\n                    newj = j - 1  # Calculate the previous column index\n                    \n                    # Check if the move is valid\n                    if 0 <= newi < m and 0 <= newj < n and grid[i][j] > grid[newi][newj] and dp[newi] == newj:\n                        dp2[i] = j  # Update the dp array for the current row\n                        maxOp = max(maxOp, j)  # Update the maximum moves if needed\n                        break  # Exit the loop after a successful move\n            \n            # Update the original dp array with the changes from dp2 for the next iteration\n            dp = dp2[:]\n        \n        # Return the maximum number of valid moves found\n        return maxOp\n```\n\n\n# Depth-First Search Solution\n```python3 []\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the number of rows and columns\n        m = len(grid)\n        n = len(grid[0])\n        \n        # Define possible movements in the row direction (up, no move, down)\n        direction = [-1, 0, 1]\n        \n        # Decorator for memoization to store results of DFS calls\n        @lru_cache(maxsize=None)\n        def dfs(i, j, count):\n            # Initialize the output with the current count\n            output = count\n            # Explore all three possible row movements\n            for ni in direction:\n                # Check if the new position is within bounds and meets the conditions for a valid move\n                if 0 <= i + ni < m and 0 < j + 1 < n and grid[i + ni][j + 1] > grid[i][j] and count + 1 == j + 1:\n                    # Recursively call dfs for the next position\n                    value = dfs(i + ni, j + 1, count + 1)\n                    # Update the output to the maximum value found\n                    if value > output:\n                        output = value\n            return output\n        \n        # Initialize the maximum count\n        maxC = 0\n        # Iterate over all rows to start the dfs from the first column\n        for i in range(m):\n            value = dfs(i, 0, 0)\n            # If the value equals n-1, return it immediately as it\'s the maximum possible\n            if value == n - 1:\n                return value\n            # Update the maximum count found\n            if value > maxC:\n                maxC = value\n        \n        # Return the maximum moves found\n        return maxC\n\n```\n\n# Breath-First Search Solution\n```python3 []\nfrom typing import List\nfrom collections import deque\n\nclass Solution:\n    def maxMoves(self, grid: List[List[int]]) -> int:\n        # Get the number of rows and columns\n        m, n = len(grid), len(grid[0])\n        \n        # Define possible movements in the row direction (up, no move, down)\n        direction = [-1, 0, 1]\n        \n        # Initialize the maximum count of valid moves\n        maxcount = 0\n        \n        # Set to keep track of visited states to avoid processing the same state multiple times\n        seen = set()\n        \n        # Iterate over all rows to start BFS from the first column\n        for idx in range(m):\n            # Initialize the queue with the starting position and move count\n            q = deque([[idx, 0, 0]])\n            while q:\n                i, j, count = q.popleft()\n                \n                # Continue if the current state has already been processed\n                if (i, j, count) in seen:\n                    continue\n                \n                # Add the current state to the seen set\n                seen.add((i, j, count))\n                \n                # Update the maximum count of moves\n                if count > maxcount:\n                    maxcount = count\n                \n                # Explore all possible directions\n                for ni in direction:\n                    if 0 <= i + ni < m and 0 < j + 1 < n and grid[i + ni][j + 1] > grid[i][j] and count + 1 == j + 1 and (i + ni, j + 1, count + 1) not in seen:\n                        q.append([i + ni, j + 1, count + 1])\n        \n        # Return the maximum number of valid moves found\n        return maxcount\n\n```
['Dynamic Programming', 'Depth-First Search', 'Breadth-First Search', 'Queue', 'Ordered Set', 'Python3']