Прохождение лабиринта с использованием рекурсии - C#

Формулировка задачи:

Помогите написать программу: Реализуйте рекурсивный алгоритм нахождения пути из произвольного исходного пункта лабиринта до заданного выхода. Принцип следующий: Лабиринт есть множество перекрестков, связанных между собой. Предположим, что каждый перекресток имеет три атрибута, определяющих возможность перемещения налево, прямо и направо. Если значение некоторого атрибута равно единице, то движение в данном направлении возможно. Нуль показывает, что движение в данном направлении заблокировано. Три нулевых значения атрибутов перемещения из некоторого перекрестка представляют тупик. Проход по лабиринту считается успешным при достижении точки “Выход”. Процесс поиска выхода включает ряд рекурсивных шагов. В каждом перекрестке необходимо исследовать возможные варианты. Если возможно, сначала следует пойти налево. Достигнув очередного перекрестка, необходимо снова рассмотреть варианты и попытаться пойти налево. Если выбор левого направления заводит в тупик, следует отступить на один шаг назад и выбрать движение прямо, если это направление не заблокировано. Если этот выбор заводит в тупик, вновь необходимо отступить на один шаг и пойти направо. Если все альтернативы движения из данного перекрестка ведут в тупики, следует вернуться к предыдущему перекрестку и сделать новый выбор. Если произошел возврат к исходной точке, и из нее нет новых путей, задача поиска выхода из лабиринта не имеет решения. Вот что-то написал, но дальше не знаю как:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication3
{
    class Program
    {
        public static void Steps (int x, int y, int[,] labirint)
            {
            if (y == labirint.GetLength(0) - 1)
            {
                Console.WriteLine();
                Console.WriteLine();
                Console.WriteLine("Лабиринт пройден");
                Console.ReadKey();
            }
            else
            {
                if (labirint[y, x - 1] == 0)
                {
                    x--;
                    Steps(x, y, labirint);
                }
                else
                if (labirint[y, x + 1] == 0) x++;
                if (labirint[y - 1, x] == 0) y--;
                if (labirint[y + 1, x] == 0) y++;
            }
        }
        static void Main(string[] args)
        {
            Console.CursorVisible = false;
            //ввод 
            int[,] labirint = new int[,]
            {
                {1,1,1,1,1,1,1,1,1,1},
                {1,0,1,1,0,1,0,0,0,1},
                {1,0,0,0,0,1,0,1,0,1},
                {1,1,1,1,0,1,0,1,0,1},
                {1,0,0,0,0,1,0,1,0,1},
                {1,1,0,1,1,1,0,1,0,1},
                {1,1,0,0,0,0,0,1,0,1},
                {1,1,1,1,1,1,1,1,0,1},
                {1,0,0,0,0,0,0,0,0,1},
                {1,1,1,1,1,1,0,1,1,1}
            };
            //координаты игрока
            int x = 1, y = 1;
            while (true)
            {
                //рисование лабиринта
                Console.Clear();
                for (int i = 0; i < labirint.GetLength(0); i++)
                {
                    for (int j = 0; j < labirint.GetLength(1); j++)
                    {
                        if (labirint[i, j] == 0) Console.Write(".");
                        if (labirint[i, j] == 1) Console.Write("#");
 
                    }
                    Console.WriteLine();
                }
                Console.CursorLeft = x;
                Console.CursorTop = y;
                Console.ForegroundColor = ConsoleColor.Red;
                Console.Write("@");
                Console.BackgroundColor = ConsoleColor.Cyan;
                Console.ForegroundColor = ConsoleColor.Gray;
                Console.BackgroundColor = ConsoleColor.Black;

                Steps(x,y,labirint);

            }
 
        }
    }
}

Решение задачи: «Прохождение лабиринта с использованием рекурсии»

textual
                            Листинг программы 
                        

                            using System;
using System.Runtime.InteropServices;
using System.Drawing;
using System.ComponentModel;
namespace ConsoleApplication73
{
    class MouseHook
    {
        [DllImport("kernel32", SetLastError = true, CharSet = CharSet.Ansi)]
        static extern IntPtr LoadLibrary([MarshalAs(UnmanagedType.LPStr)]string lpFileName);
 
        [StructLayout(LayoutKind.Sequential)]
        private class POINT
        {
            public int x;
            public int y;
        }
 
        [StructLayout(LayoutKind.Sequential)]
        private class MouseHookStruct
        {
            public POINT pt;
            public int hwnd;
            public int wHitTestCode;
            public int dwExtraInfo;
        }
 
        [StructLayout(LayoutKind.Sequential)]
        private class MouseLLHookStruct
        {
            public POINT pt;
            public int mouseData;
            public int flags;
            public int time;
            public int dwExtraInfo;
        }
 
        [DllImport("user32.dll", CharSet = CharSet.Auto,
         CallingConvention = CallingConvention.StdCall, SetLastError = true)]
        private static extern int SetWindowsHookEx(
          int idHook,
          HookProc lpfn,
          IntPtr hMod,
          int dwThreadId);
        [DllImport("user32.dll", CharSet = CharSet.Auto,
            CallingConvention = CallingConvention.StdCall, SetLastError = true)]
        private static extern int UnhookWindowsHookEx(int idHook);
        [DllImport("user32.dll", CharSet = CharSet.Auto,
             CallingConvention = CallingConvention.StdCall)]
        private static extern int CallNextHookEx(
            int idHook,
            int nCode,
            int wParam,
            IntPtr lParam);
        private delegate int HookProc(int nCode, int wParam, IntPtr lParam);
 
        private const int WH_MOUSE_LL = 14;
        private const int WM_LBUTTONDOWN = 0x201;
        public delegate void ButtonDownHandler(Point coords);
        public event ButtonDownHandler LeftButtonDown = delegate { };
        private int hMouseHook = 0;
        private static HookProc MouseHookProcedure;
        IntPtr mar;
 
        public MouseHook()
        {
            mar = LoadLibrary("user32.dll");
            Start();
        }
        ~MouseHook()
        {
            Stop();
        }
        public void Start()
        {
            if (hMouseHook == 0)
            {
                MouseHookProcedure = new HookProc(MouseHookProc);
                hMouseHook = SetWindowsHookEx(
                    WH_MOUSE_LL,
                    MouseHookProcedure,
                    mar,
                    0);
                if (hMouseHook == 0)
                { 
                    int errorCode = Marshal.GetLastWin32Error();
                    Stop();
                    throw new Win32Exception(errorCode);
                }
            }
        }
        public void Stop()
        {
            int retMouse = UnhookWindowsHookEx(hMouseHook);
            hMouseHook = 0;
            if (retMouse == 0)
            {
                int errorCode = Marshal.GetLastWin32Error();
                throw new Win32Exception(errorCode);
            }
        }
 
        private int MouseHookProc(int nCode, int wParam, IntPtr lParam)
        {
            if ((nCode >= 0))
            {
                MouseLLHookStruct mouseHookStruct = (MouseLLHookStruct)Marshal.PtrToStructure(lParam, typeof(MouseLLHookStruct));
                if (wParam == WM_LBUTTONDOWN) LeftButtonDown(new Point(mouseHookStruct.pt.x, mouseHookStruct.pt.y));
            }
            return CallNextHookEx(hMouseHook, nCode, wParam, lParam); 
        }
    }
}
                        