C# Solution for Maximum Number of Moves In a Grid Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves finding the maximum number of valid moves across a matrix, where e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves finding the maximum number of valid moves across a matrix, where each move requires navigating to a cell with a strictly higher value in one of three directions (right, top-right, or bottom-right). Starting from any cell in the first column, our goal is to reach as far as possible by following these rules.\n\nInstead of recursively exploring each path (as in DFS), we can use Breadth-First Search (BFS). BFS explores each level of moves simultaneously, which allows us to explore all possible moves from each cell level-by-level. This level-based expansion naturally finds the longest path by tracking the depth of each level in BFS.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tInitialize BFS from First Column:\n\t\u2022\tFor each cell in the first column, initialize a BFS. This will explore all paths starting from each of these cells.\n\t\u2022\tUse a queue to store each cell\u2019s coordinates along with the current move count. For each starting point, initiate BFS with a move count of zero.\n2.\tExpand BFS Level-by-Level:\n\t\u2022\tFor each cell dequeued from the queue, attempt to move in each of the three possible directions (right, top-right, and bottom-right).\n\t\u2022\tOnly enqueue cells that are in bounds, have a greater value than the current cell, and have not been visited within the current BFS traversal.\n\t\u2022\tTrack the maximum moves reached during BFS from any starting cell in the first column.\n3.\tTrack Maximum Move Count:\n\t\u2022\tMaintain a variable (maxMoves) to track the longest path of moves reached across all BFS traversals.\n4.\tEdge Case Handling:\n\t\u2022\tIf no valid moves are possible from any starting cell, the solution will correctly return 0.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(m x n):\n\u2022\tEach cell in the matrix is visited at most once for each starting BFS (one per row in the first column).\n\u2022\tThe BFS traversals are efficient as each cell is processed only once due to the use of a visited array, which avoids redundant processing within each BFS.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m x n):\n\u2022\tThe visited array requires O(m x n) space to track whether each cell has been processed in the current BFS traversal.\n\u2022\tThe queue for BFS can store up to O(m x n) elements in the worst case, but generally remains manageable within the grid size.\n\n# Code\n```csharp []\npublic class Solution {\n    public int MaxMoves(int[][] grid) {\n        int m = grid.Length;\n        int n = grid[0].Length;\n        int maxMoves = 0;\n\n        // Directions for moving right, top-right, and bottom-right\n        int[][] directions = new int[][] {\n            new int[] {0, 1},  // Move right\n            new int[] {-1, 1}, // Move top-right\n            new int[] {1, 1}   // Move bottom-right\n        };\n        \n        // Initialize BFS queue for each cell in the first column\n        for (int row = 0; row < m; row++) {\n            Queue<(int, int, int)> queue = new Queue<(int, int, int)>();\n            queue.Enqueue((row, 0, 0));  // Start from column 0 with move count 0\n            bool[,] visited = new bool[m, n];\n            visited[row, 0] = true;\n            \n            while (queue.Count > 0) {\n                var (curRow, curCol, moves) = queue.Dequeue();\n                maxMoves = Math.Max(maxMoves, moves);\n                \n                // Explore all directions\n                foreach (var dir in directions) {\n                    int newRow = curRow + dir[0];\n                    int newCol = curCol + dir[1];\n                    \n                    if (newRow >= 0 && newRow < m && newCol < n && !visited[newRow, newCol] \n                        && grid[newRow][newCol] > grid[curRow][curCol]) {\n                        queue.Enqueue((newRow, newCol, moves + 1));\n                        visited[newRow, newCol] = true;\n                    }\n                }\n            }\n        }\n        \n        return maxMoves;\n    }\n}\n```
['C#']