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

@SL3W · Регистрация: 09.03.2016

Студворк — интернет-сервис помощи студентам

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

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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);
 
                
            }
 
        }
    }
}

@JIoB3uK · 09.03.2016, 18:01

если нет задачи найти кратчайший путь, я бы для поиска выхода исопльзовал древний как мир, метод "левой руки".
суть в том, что человек касается рукой одной стены и идет все время держась за нее. так он обойдет все стены лабиринта и дойдет к выходу. ну либо вернется на место.
т.е. проверяем текущее положение, и сосденюю клетку. если упираемся в стену, делаем поворот на 90 градусов. Всё, больше ничего ненадо для поиска. в тупике он повернется один раз, проверит, шаг сделать не может (или может, если "широкий кориодор". и так обходим всё. но это для условия что лабиринт именно лабиринт коридоров.
http://image.slidesharecdn.com... 13-728.jpg

@SL3W · 09.03.2016, 18:09 **[ТС]**

Сообщение от JIoB3uK

если нет задачи найти кратчайший путь, я бы для поиска выхода исопльзовал древний как мир, метод "левой руки".
суть в том, что человек касается рукой одной стены и идет все время держась за нее. так он обойдет все стены лабиринта и дойдет к выходу. ну либо вернется на место.
т.е. проверяем текущее положение, и сосденюю клетку. если упираемся в стену, делаем поворот на 90 градусов. Всё, больше ничего ненадо для поиска. в тупике он повернется один раз, проверит, шаг сделать не может (или может, если "широкий кориодор". и так обходим всё. но это для условия что лабиринт именно лабиринт коридоров.
http://image.slidesharecdn.com... 13-728.jpg

нет, нужен именно рекурсивный проход по тому принципу, который я написал

@EvilFromHell · 09.03.2016, 23:40

Мой вариант:
Класс "Лабиринт":

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Drawing;
 
namespace WindowsFormsApplication55
{
    class Labyrinth
    {
 
        public Labyrinth(int[,] arr):this(arr,new Point(0,0),new Size(30,30))
        {}
 
        public Labyrinth(int[,] arr,Point location): this(arr, location, new Size(30, 30))
        { }
 
        public Labyrinth(int[,] arr, Point location, Size cellsize)
        {
            cells = FromIntArray(arr);
            LabyrinthCell.Size = cellsize;
            Location = location;
        }
        private Point location;
        public Point Location { get { return location; }
        set
            {
                location = value;
                for (int i = 0; i < cells.GetLength(0); i++)
                    for (int j = 0; j < cells.GetLength(1); j++)
                        cells[i,j].Location = new Point(this.Location.X + i * LabyrinthCell.Size.Width, this.Location.Y + j * LabyrinthCell.Size.Height);
            }
        }
 
        private List<EmptyCell> SelectedCells = new List<EmptyCell>();
        private List<Point> CrossedPoints = new List<Point>();
        public Size CellSize { get { return LabyrinthCell.Size; } set { LabyrinthCell.Size = value; Location = location; } }
 
        public Size Size { get { return new Size(LabyrinthCell.Size.Width * cells.GetLength(0), LabyrinthCell.Size.Height * cells.GetLength(1)); } }
 
        public Rectangle Rect { get { return new Rectangle(Location, Size); } }
 
 
        public bool SetPath()
        {
            if (SelectedCells.Count != 2) return false;
            foreach (EmptyCell cl in AllCells().Where(x => (typeof(EmptyCell) == x.GetType()))) cl.Crossed = false;
            CrossedPoints.Clear();
            bool result = SetPathRecursive(new List<EmptyCell>(), SelectedCells[0], SelectedCells[1]);
            if(result)CrossedPoints.Add(new Point(SelectedCells[0].Location.X + LabyrinthCell.Size.Width / 2, SelectedCells[0].Location.Y + LabyrinthCell.Size.Height / 2));
            else CrossedPoints.Clear();
            return result;
        } 
        public bool SetPathRecursive(List<EmptyCell> used,EmptyCell current,EmptyCell end)
        {
            if (current == end) return true;
            used.Add(current);
            foreach (EmptyCell cell in current.Connections)
                if (!used.Contains(cell))
                    if (SetPathRecursive(used, cell,end))
                    {
                        cell.Crossed = true;
                        CrossedPoints.Add(new Point(cell.Location.X+LabyrinthCell.Size.Width/2, cell.Location.Y + LabyrinthCell.Size.Height / 2));
                        return true;
                    }
            return false;
        }
 
 
        public bool ClickAndSetPath(Point p)
        {
            EmptyCell cell = (EmptyCell)AllCells().FirstOrDefault(x => x.Rect.Contains(p) && x.GetType() == typeof(EmptyCell));
            if (cell != null)
            {
                if (cell.Selected) { SelectedCells.Remove(cell); CrossedPoints.Clear(); }
                else { if (SelectedCells.Count > 1) return true; SelectedCells.Add(cell); }
                cell.Selected = !cell.Selected;
                if (SelectedCells.Count == 2)
                {
                    bool res = SetPath();
                    if (!res) { SelectedCells.Remove(cell); cell.Selected = false; }
                    return res;
                }
            }
            return true;
        }
        private IEnumerable<LabyrinthCell> AllCells()
        {
            for (int i = 0; i < cells.GetLength(0); i++)
                for (int j = 0; j < cells.GetLength(1); j++)
                    yield return cells[i, j];
        }
        private LabyrinthCell[,] cells;
        private LabyrinthCell[,] FromIntArray(int[,] arr)
        {
            LabyrinthCell[,] res = new LabyrinthCell[arr.GetLength(0), arr.GetLength(1)];
            int m = arr.GetLength(0);
            int n = arr.GetLength(1);
            for (int i=0;i< m;i++)
                for (int j = 0; j < n; j++)
                {
                    if (res[i, j] == null)
                    {
                        if (arr[i, j] == 0)
                        {
                            res[i, j] = new EmptyCell();
                        }
                        else { res[i, j] = new FilledCell(); continue; }
                    }
                    else if (typeof(EmptyCell) != res[i, j].GetType()) continue;
                    var cell = (EmptyCell)res[i, j];
                    cell.Location = new Point(this.Location.X + i * LabyrinthCell.Size.Width, this.Location.Y + j * LabyrinthCell.Size.Height);
                    foreach (Point p in patternPoints)
                    {
                        var current = new Point(i, j);
                        current.Offset(p.X, p.Y);
                        if (new Rectangle(0, 0, m, n).Contains(current))
                        {
                            if (arr[current.X, current.Y] == 0)
                            {
                                if (res[current.X, current.Y] == null)
                                {
                                    var newcell = new EmptyCell();
                                    res[current.X, current.Y] = newcell;
                                    cell.Connections.Add(newcell);
                                }
                                else cell.Connections.Add((EmptyCell)res[current.X, current.Y]);
                            }
                            else { if (res[current.X, current.Y] == null) res[current.X, current.Y] = new FilledCell(); }
                        }
                     }
                }
            return res;
         }
 
        private static Point[] patternPoints = new Point[] {
            new Point(-1, 0),
            new Point(0, -1),
            new Point(1, 0),
            new Point(0, 1),
            };
        public void Draw(Graphics g)
        {
            foreach (LabyrinthCell cl in AllCells()) cl.Draw(g);
            if(CrossedPoints.Count>0)
            g.DrawLines(Pens.Red, CrossedPoints.ToArray());
        }
 
        public abstract class LabyrinthCell
        {
            public Rectangle Rect { get { return new Rectangle(Location, Size); } }
            public static Size Size { get; set; } = new Size(20, 20);
            public Point Location { get; set; }
            public abstract void Draw(Graphics g);
        }
 
        public class EmptyCell : LabyrinthCell
        {
            public bool Selected { get; set; } = false;
            public bool Crossed { get; set; } = false;
            public override void Draw(Graphics g)
            {
                if (Selected) g.FillRectangle(Brushes.Pink, this.Rect);
            }
            public List<EmptyCell> Connections = new List<EmptyCell>();
        }
 
        public class FilledCell : LabyrinthCell
        {
            public override void Draw(Graphics g)
            {
                g.FillRectangle(Brushes.Blue,new Rectangle(Location,Size));
            }
        }
    }
}

Использование:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using System.Windows.Forms;
 
namespace WindowsFormsApplication55
{
    public partial class Form1 : Form
    {
        Labyrinth LB = new Labyrinth(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,1,0,1},
                {1,1,1,1,1,1,0,1,1,1}
            });
        public Form1()
        {
            InitializeComponent();
        }
 
        private void Form1_MouseClick(object sender, MouseEventArgs e)
        {
            if (!LB.ClickAndSetPath(e.Location)) MessageBox.Show("Нет пути");
            this.Invalidate();
        }
 
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            LB.Draw(e.Graphics);
        }
    }
}

@EvilFromHell · 09.03.2016, 23:42

Код особо не отлаживался, местами, возможно, говнокод, но вроде бы все работает

@SL3W · 10.03.2016, 14:25 **[ТС]**

Сообщение от EvilFromHell

Код особо не отлаживался, местами, возможно, говнокод, но вроде бы все работает

а можешь архивом кинуть?

Добавлено через 1 минуту

Сообщение от EvilFromHell

Код особо не отлаживался, местами, возможно, говнокод, но вроде бы все работает

и можешь сделать это в консоли, как у меня было?

@EvilFromHell · 10.03.2016, 14:29

SL3W, а нафига это все лепить в консоль? Можно, конечно, и там отобразить, но так неудобно же.

Сообщение от SL3W

а можешь архивом кинуть?

Чего тут кидать-для работы достаточно просто скопипастить код в новый проект. Он не требует расстановки каких-либо контролов. Кнопку я тупо забыл убрать.

@SL3W · 11.03.2016, 11:11 **[ТС]**

Сообщение от EvilFromHell

SL3W, а нафига это все лепить в консоль? Можно, конечно, и там отобразить, но так неудобно же.

Чего тут кидать-для работы достаточно просто скопипастить код в новый проект. Он не требует расстановки каких-либо контролов. Кнопку я тупо забыл убрать.

да мне именно в консоли надо

Добавлено через 4 часа 32 минуты
Есть новый вариант, но все равно работает не полностью

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
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, string laststep)
        {
            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;
 
 
                int savex = 1;
                int saveY = 1;
                if (y == labirint.GetLength(0) - 1)
                {
                    Console.WriteLine();
                    Console.WriteLine();
                    Console.WriteLine("Лабиринт пройден");
                    Console.ReadKey();
 
                    break;
                }
                else
                {
 
                    if (labirint[y, x - 1] == 0 && laststep !="right")
                    {
                        savex = x;
                        saveY = y;
                        x--;
                        laststep = "left";
                        Console.ReadKey();
                        if (labirint[y - 1, x] == 1 && labirint[y, x + 1] == 1 && labirint[y+1, x] == 1)
                            laststep = null;
                        Steps(x, y, labirint,laststep);
                    }
                    else
                    {
                        if (labirint[y, x + 1] == 0 && laststep !="left")
                        {
                            savex = x;
                            saveY = y;
                            x++;
                            laststep = "right";
                            Console.ReadKey();
                            if (labirint[y + 1, x] == 1 && labirint[y-1, x] == 1 && labirint[y, x - 1] == 1)
                                laststep = null;
                            Steps(x, y, labirint, laststep); 
                        }
                        else
                        {
                            if (labirint[y - 1, x] == 0 && laststep !="down")
                            {
                                savex = x;
                                saveY = y;
                                y--;
                                laststep = "up";
                                Console.ReadKey();
                                if (labirint[y + 1, x] == 1 && labirint[y, x + 1] == 1 && labirint[y, x - 1] == 1)
                                    laststep = null;
                                Steps(x, y, labirint, laststep);
                            }
                            else
                            {
                                if (labirint[y + 1, x] == 0 && laststep!="up")
                                {
                                    savex = x;
                                    saveY = y;
                                    y++;
                                    laststep = "down";
                                    Console.ReadKey();
                                    if (labirint[y - 1, x] == 1 && labirint[y, x + 1] == 1 && labirint[y, x - 1] == 1)
                                        laststep = null;
                                    Steps(x, y, labirint, laststep);
                                }
                                else
                                {
 
                                    laststep = null;
                                    Steps(savex, saveY, labirint, laststep);
                                }
                            }
                        }
                    }
                }
            }
        }
 
        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,0,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,0,1,1,1,1,1,1,1,1}
            };
            //координаты игрока
            int x = 1, y = 1;
 
 
            string laststep = null;
                Steps(x, y, labirint, laststep);
 
 
            
 
        }
    }
}

@EvilFromHell · 11.03.2016, 15:27

Ок, никаких винформ, только консоль, только хардкор

Program.cs

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using System;
using System.Timers;
using System.Drawing;
using System.Runtime.InteropServices;
using System.Diagnostics;
 
namespace ConsoleApplication73
{
    class Program
    {
        #region WinApi
        [DllImport("user32.dll")]
        static extern bool ScreenToClient(IntPtr hWnd, ref POINT lpPoint);
        public struct POINT
        {
            public int X;
            public int Y;
 
            public POINT(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
 
            public POINT(System.Drawing.Point pt) : this(pt.X, pt.Y) { }
 
            public static implicit operator System.Drawing.Point(POINT p)
            {
                return new System.Drawing.Point(p.X, p.Y);
            }
 
            public static implicit operator POINT(System.Drawing.Point p)
            {
                return new POINT(p.X, p.Y);
            }
        }
 
        public class NativeMethods
        {
            [Serializable]
            public struct MSG
            {
                public IntPtr hwnd;
                public IntPtr lParam;
                public int message;
                public int pt_x;
                public int pt_y;
                public int time;
                public IntPtr wParam;
            }
 
            [DllImport("user32.dll")]
            public static extern bool GetMessage(out MSG lpMsg, IntPtr hWnd, uint wMsgFilterMin, uint wMsgFilterMax);
 
            [DllImport("user32.dll")]
            public static extern bool TranslateMessage([In] ref MSG lpMsg);
 
            [DllImport("user32.dll")]
            public static extern IntPtr DispatchMessage([In] ref MSG lpmsg);
        }
        #endregion
 
        static Labyrinth LB = new Labyrinth(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}
    });
 
        public static object locker = new object();
        static void Main(string[] args)
        {
            var handle = Process.GetCurrentProcess().MainWindowHandle;
            Graphics g = Graphics.FromHwnd(handle);
            Draw(g);
            MouseHook hook = new MouseHook();
            hook.LeftButtonDown += (p) =>
            {
                POINT pnt = new POINT(p);
                ScreenToClient(handle, ref pnt);
                LB.ClickAndSetPath(pnt);
                Draw(g);
            };
            Timer timer = new Timer();
            timer.Interval = 1000;
            timer.Elapsed += (s, e) => Draw(g);
            timer.Start();
            NativeMethods.MSG msg;
            while ((NativeMethods.GetMessage(out msg, IntPtr.Zero, 0, 0)))
            {
                NativeMethods.TranslateMessage(ref msg);
                NativeMethods.DispatchMessage(ref msg);
            }
        }
        public static void Draw(Graphics g)
        {
            lock (locker)
            {
                g.FillRectangle(Brushes.White, LB.Rect); LB.Draw(g);
            }
        }
 
    }
}

MouseHook.cs

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
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); 
        }
    }
}

@EvilFromHell · 11.03.2016, 15:30

Класс Labyrinth не изменился.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@JIoB3uK 5 / 5 / 7 Регистрация: 09.03.2016 Сообщений: 89
	09.03.2016, 18:01
	если нет задачи найти кратчайший путь, я бы для поиска выхода исопльзовал древний как мир, метод "левой руки". суть в том, что человек касается рукой одной стены и идет все время держась за нее. так он обойдет все стены лабиринта и дойдет к выходу. ну либо вернется на место. т.е. проверяем текущее положение, и сосденюю клетку. если упираемся в стену, делаем поворот на 90 градусов. Всё, больше ничего ненадо для поиска. в тупике он повернется один раз, проверит, шаг сделать не может (или может, если "широкий кориодор". и так обходим всё. но это для условия что лабиринт именно лабиринт коридоров. http://image.slidesharecdn.com... 13-728.jpg 0

@EvilFromHell 979 / 874 / 350 Регистрация: 26.04.2012 Сообщений: 2,647
	09.03.2016, 23:42
	Код особо не отлаживался, местами, возможно, говнокод, но вроде бы все работает 0

@EvilFromHell 979 / 874 / 350 Регистрация: 26.04.2012 Сообщений: 2,647
	11.03.2016, 15:30
	Класс Labyrinth не изменился. 0

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

Решение