C || JAVA || C++ || Python || 👍💫Maximum Number of Moves in a Grid
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition here is to use DFS to explore each valid path from the leftmost column, c
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition here is to use DFS to explore each valid path from the leftmost column, checking if each step is strictly increasing. By keeping track of the maximum path length across all starting points, the algorithm finds the longest increasing sequence of moves that only progresses rightward. This approach leverages DFS and backtracking to efficiently explore possible paths while avoiding redundant checks.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach for the provided C code is a Depth-First Search  algorithm that explores possible paths from each cell in the first column of a grid. The goal is to find the maximum number of moves where each move goes to an adjacent cell in one of three possible directions (up-right, right, or down-right) and has a strictly increasing value.\n1) Start from any value in the first column.\n2) For each cell, recursively move to any of the three rightward directions if the move is within bounds and strictly increases the value.\n3) Update the maximum moves or calls for each DFS cycle.\n# Complexity\n- Time complexity : O(m X n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : O(n) for the recursion stack \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# PLEASE UPVOTE !! \n\n# Code\n```c []\nconst int move[3][2] = {{-1,1}, {0,1}, {1,1}};\n\nvoid dfs(int** grid, const int m, const int n, int x, int y, int cnt, int* ret) {\n    for (int i = 0; i < 3; ++i) {\n        int nx = x + move[i][0], ny = y + move[i][1];\n        \n        if (nx < 0 || nx == m || ny == n)\n            continue;\n        \n        if (grid[x][y] < grid[nx][ny]) {\n            dfs(grid, m, n, nx, ny, cnt + 1, ret);\n            grid[nx][ny] = 0;\n        }\n    }\n    \n    *ret = *ret < cnt ? cnt : *ret;\n}\n\nint maxMoves(int** grid, int gridSize, int* gridColSize) {\n    int ret = 0;\n        \n    for (int i = 0; i < gridSize; ++i) {\n        dfs(grid, gridSize, *gridColSize, i, 0, 0, &ret);\n    }\n        \n    return ret;\n}\n\n```\n```Java []\nclass Solution {\n    private static final int[][] moves = {{-1, 1}, {0, 1}, {1, 1}};\n\n    public int maxMoves(int[][] grid) {\n        int m = grid.length;\n        int n = grid[0].length;\n        int result = 0;\n\n        // Start DFS from each row in the first column\n        for (int i = 0; i < m; i++) {\n            result = Math.max(result, dfs(grid, m, n, i, 0, 0));\n        }\n\n        return result;\n    }\n\n    private int dfs(int[][] grid, int m, int n, int x, int y, int count) {\n        int maxCount = count;\n\n        for (int[] move : moves) {\n            int nx = x + move[0];\n            int ny = y + move[1];\n\n            // Check boundaries and strictly increasing condition\n            if (nx >= 0 && nx < m && ny < n && grid[x][y] < grid[nx][ny]) {\n                maxCount = Math.max(maxCount, dfs(grid, m, n, nx, ny, count + 1));\n                grid[nx][ny] = 0;  // Mark the cell to avoid revisits\n            }\n        }\n\n        return maxCount;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int maxMoves(std::vector<std::vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        int result = 0;\n\n        // Start DFS from each row in the first column\n        for (int i = 0; i < m; ++i) {\n            result = std::max(result, dfs(grid, m, n, i, 0, 0));\n        }\n\n        return result;\n    }\n\nprivate:\n    const int moves[3][2] = {{-1, 1}, {0, 1}, {1, 1}};\n\n    int dfs(std::vector<std::vector<int>>& grid, int m, int n, int x, int y, int count) {\n        int maxCount = count;\n\n        for (int i = 0; i < 3; ++i) {\n            int nx = x + moves[i][0];\n            int ny = y + moves[i][1];\n\n            // Check boundaries and strictly increasing condition\n            if (nx >= 0 && nx < m && ny < n && grid[x][y] < grid[nx][ny]) {\n                maxCount = std::max(maxCount, dfs(grid, m, n, nx, ny, count + 1));\n                grid[nx][ny] = 0;  // Mark the cell to avoid revisits\n            }\n        }\n\n        return maxCount;\n    }\n};\n```\n```PYTHON []\nclass Solution:\n    def __init__(self):\n        # Define the possible moves (up-right, right, down-right)\n        self.moves = [(-1, 1), (0, 1), (1, 1)]\n    \n    def maxMoves(self, grid):\n        m, n = len(grid), len(grid[0])\n        result = 0\n\n        # Start DFS from each row in the first column\n        for i in range(m):\n            result = max(result, self.dfs(grid, m, n, i, 0, 0))\n\n        return result\n\n    def dfs(self, grid, m, n, x, y, count):\n        max_count = count\n\n        for dx, dy in self.moves:\n            nx, ny = x + dx, y + dy\n\n            # Check boundaries and strictly increasing condition\n            if 0 <= nx < m and ny < n and grid[x][y] < grid[nx][ny]:\n                max_count = max(max_count, self.dfs(grid, m, n, nx, ny, count + 1))\n                grid[nx][ny] = 0  # Mark the cell to avoid revisits\n\n        return max_count\n```
['C']