using System;
using System.Diagnostics;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] maze = {
            { -1, 0, 1, 0, 3 },
            { 1, 0, 1, 0, 1 },
            { 0, 0, 0, 0, 1 },
            { 1, 1, 1, 0, 0 },
            { 1, 1, 0, 0, 1 }
        };

        Stopwatch stopwatch = Stopwatch.StartNew();
        int shortestPath = FindShortestPath(maze);
        stopwatch.Stop();

        if (shortestPath != -1)
            Console.WriteLine($"Jarak terpendek ke angka 3 adalah: {shortestPath} langkah.");
        else
            Console.WriteLine("Tidak ada jalur ke angka 3.");

        Console.WriteLine($"Waktu eksekusi: {stopwatch.ElapsedMilliseconds} ms");
    }

    static int FindShortestPath(int[,] maze)
    {
        int rows = maze.GetLength(0);
        int cols = maze.GetLength(1);
        (int x, int y) start = (-1, -1);

        // Cari posisi awal (-1)
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (maze[i, j] == -1)
                {
                    start = (i, j);
                    break;
                }
            }
            if (start.x != -1) break;
        }

        if (start == (-1, -1))
            return -1; // Tidak ada posisi awal

        // Queue untuk BFS
        Queue<(int x, int y, int distance)> queue = new Queue<(int, int, int)>();
        queue.Enqueue((start.x, start.y, 0));

        // Array untuk mengatur arah gerakan (atas, bawah, kiri, kanan)
        int[] dx = { -1, 1, 0, 0 };
        int[] dy = { 0, 0, -1, 1 };

        // Set untuk melacak posisi yang sudah dikunjungi
        bool[,] visited = new bool[rows, cols];
        visited[start.x, start.y] = true;

        while (queue.Count > 0)
        {
            var (x, y, distance) = queue.Dequeue();

            // Jika ditemukan angka 3
            if (maze[x, y] == 3)
                return distance;

            // Mengecek empat arah
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx, ny] && maze[nx, ny] != 1)
                {
                    visited[nx, ny] = true;
                    queue.Enqueue((nx, ny, distance + 1));
                }
            }
        }

        return -1; // Tidak ada jalur ke angka 3
    }
}