מריה בוטוסוב

בגריד נתון של אפסים ואחדים, יש לנו שורה ועמודה התחלתיים sr, sc ושורה ועמודה יעד tr, tc. החזירו את אורך הנתיב הקצר ביותר מ-sr, sc ל-tr, tc שהולך לאורך ערכי 1 בלבד. כל מיקום בנתיב, כולל ההתחלה והסוף, חייב להיות 1. כל מיקום עוקב בנתיב חייב להיות מצמיד בארבע הכיוונים למיקום הקודם. מובטח ש-grid[sr][sc] = grid[tr][tc] = 1, והמיקומים ההתחלתי והיעד שונים. אם המשימה בלתי אפשרית, החזירו -1. Time Complexity = O(N), Space O(N)

public static int ShortestCellPath(int[,] grid, int sr, int sc, int tr, int tc)
{
    int rows = grid.GetLength(0);
    int cols = grid.GetLength(1);
    var visited = new bool[rows, cols];
    var queue = new Queue<(int, int, int)>();
    queue.Enqueue((sr, sc, 0));
    visited[sr, sc] = true;
    int[,] directions = new int[,] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    while (queue.Count > 0)
    {
        var (row, col, steps) = queue.Dequeue();
        if (row == tr && col == tc)
        {
            return steps;
        }
 
        for (int i = 0; i < directions.GetLength(0); i++) 
        {
            int nRow = row + directions[i, 0];
            int nCol = col + directions[i, 1];
            // Check if the new position is within bounds, is a 1, and not visited
            if (nRow >= 0 && nRow < rows && nCol >= 0 && nCol < cols && grid[nRow, nCol] == 1 && !visited[nRow, nCol])
            {
                    queue.Enqueue((nRow, nCol, steps + 1));
                    visited[nRow, nCol] = true;
            }
        }
    }
 
    return -1;
}
 
static void Main(string[] args)
{
    int[,] grid = {
        {1, 1, 1, 1},
        {0, 0, 0, 1},
        {1, 1, 1, 1}
    };
    int sr = 0, sc = 0, tr = 2, tc = 0;
    int result = ShortestCellPath(grid, sr, sc, tr, tc);
    Console.WriteLine($"Shortest path length: {result}");
}