using System; using System.Collections.Generic; class Solution { public static List PathTraverse(int[,] grid, int startRow, int startCol) { int rows = grid.GetLength(0); int cols = grid.GetLength(1); // Check the validity of the input if (startRow < 0 || startRow >= rows || startCol < 0 || startCol >= cols) { throw new ArgumentException("Invalid input"); } // Define all four possible directions of movement int[,] directions = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} }; // Start with the value at the starting cell List visited = new List(); visited.Add(grid[startRow, startCol]); while (true) { // Initialize the current maximum as negative one int currMax = -1; int nextRow = -1, nextCol = -1; // Loop over each adjacent cell in all the directions for (int i = 0; i < directions.GetLength(0); i++) { // Calculate the new cell's row and column indices int newRow = startRow + directions[i, 0]; int newCol = startCol + directions[i, 1]; // If the new cell is out of the grid boundary, ignore it if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols) { continue; } // If the new cell's value is greater than the current maximum if (grid[newRow, newCol] > currMax) { // Save it as the next cell to visit nextRow = newRow; nextCol = newCol; currMax = grid[newRow, newCol]; } } // If we don't have any valid cell to visit, break from the loop if (currMax <= grid[startRow, startCol]) { break; } // Otherwise, go to the next cell startRow = nextRow; startCol = nextCol; // Append the cell's value to the result list visited.Add(currMax); } // Return the list of visited cells' values return visited; } public static void Main(string[] args) { int[,] grid = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; List res = PathTraverse(grid, 1, 1); foreach (int val in res) { Console.Write(val + " "); } Console.WriteLine(); // Outputs: 5 8 9 } }