Прохождение лабиринта с использованием рекурсии - 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);
}
}
}