Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
1

Поиск кратчайшего пути лошадью

27.01.2015, 12:10. Просмотров 995. Ответов 5
Метки нет (Все метки)

(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p клеток в одном направлении, и на q - в другом (перпендикулярном). Например, (3, 4)-лошадь может переместиться с клетки (5, 6) на клетки (1, 3), (2, 2), (2, 10), (1, 9), (8, 10), (9, 9), (8, 2) и (9, 3). Очевидно, что обычный шахматный конь - это (2, 1)-лошадь.

Ваша задача - определить минимальное число ходов, которое требуется (p, q)-лошади, чтобы добраться от одной клетки шахматной доски M×N до другой. За пределы доски выходить запрещается.
Единственная строчка во входном файле содержит 8 целых чисел M, N, p, q, x1, y1, x2, y2 (1 ≤ x1, x2 ≤ M ≤ 100, 1 ≤ y1, y2 ≤ N ≤ 100, 0 ≤ p ≤ 100, 0 ≤ q ≤ 100).
Выходные данные

Первая строка выходного файла должна содержать целое число k - число ходов, которое требуется (p, q)-лошади, чтобы добраться из клетки (x1, y1) в клетку (x2, y2). Далее должна следовать k+1 строка, содержащая последовательные положения (p, q)-лошади на этом пути.

Если (p, q)-лошадь не может добраться из (x1, y1) в (x2, y2), выведите в выходной файл единственное число -1.
Набросал нечто такое
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Horse
{
    public class Node
    {
        public List<Node> data = new List<Node>();
 
        public int x;
        public int y;
        public int Mark = -1;
        public Node Way;
        public  void Numerator(ref int mark, Node node)
        {
            //Mark = mark;
            mark++;
            int newMark = mark;
            Way = node;
            if(data.Count>0)
                foreach(Node n in data)
                {
                    if (n.Mark == -1)
                    n.Mark=mark;
                }
            foreach (Node n in data)
            {
                if (n.Mark == mark)
                    n.Numerator(ref newMark, this);
                //newMark = mark;
            }
        }
        public void GetWay(List<Node> FullWay)
        {
            FullWay.Add(this.Way);
            if(Way.Mark!=0)
            {
                Way.GetWay(FullWay);
            }
        }
    }
 
 
    class Program
    {
        static void Main(string[] args)
        {
            System.IO.StreamReader file = new System.IO.StreamReader(@"horse.in");
            string[] arr = file.ReadLine().Split(' ');
            int M, N, p, q, x1, y1, x2, y2;
            M = int.Parse(arr[0]);
            N = int.Parse(arr[1]);
            p = int.Parse(arr[2]);
            q = int.Parse(arr[3]);
            x1 = int.Parse(arr[4]);
            x1--;
            y1 = int.Parse(arr[5]);
            y1--;
            x2 = int.Parse(arr[6]);
            x2--;
            y2 = int.Parse(arr[7]);
            y2--;
 
 
            Node[,] desk = new Node[M, N];
            for(int i = 0; i<M; ++i)
                for (int j = 0; j < N; ++j)
                {
                    desk[i, j] = new Node();
                    desk[i, j].x = i;
                    desk[i, j].y = j;
                }
 
            for(int i = 0; i<M; ++i)
                for(int j = 0; j< N; ++j)
                {
 
                    if(j+q<N)
                    {
                        if(i+p<M)
                        {
                            if (!desk[i, j].data.Contains(desk[i + p, j + q]))
                            desk[i,j].data.Add(desk[i + p,j + q]);
                        }
                        if (i - p >= 0)
                        {
                            if (!desk[i, j].data.Contains(desk[i - p, j + q]))
                            desk[i,j].data.Add(desk[i - p,j + q]);
                        }
 
                    }
 
                    if (j - q >= 0)
                    {
                        if (i + p < M)
                        {
                            if (!desk[i, j].data.Contains(desk[i + p, j - q]))
                            desk[i,j].data.Add(desk[i + p,j - q]);
                        }
                        if (i - p >= 0)
                        {
                            if (!desk[i, j].data.Contains(desk[i - p, j - q]))
                            desk[i,j].data.Add(desk[i - p,j - q]);
                        }
 
                    }
                    if (j + p < N)
                    {
                        if (i + q < M)
                        {
                            if (!desk[i, j].data.Contains(desk[i + q, j + p]))
                            desk[i,j].data.Add(desk[i + q,j + p]);
                        }
                        if (i - q >= 0)
                        {
                            if (!desk[i, j].data.Contains(desk[i - q, j + p]))
                            desk[i,j].data.Add(desk[i - q,j + p]);
                        }
 
                    }
                    if (j - p >= 0)
                    {
                        if (i + q < M)
                        {
                            if (!desk[i, j].data.Contains(desk[i + q, j - p]))
                            desk[i,j].data.Add(desk[i + q,j - p]);
                        }
                        if (i - q >= 0)
                        {
                            if (!desk[i, j].data.Contains(desk[i - q, j - p]))
                            desk[i,j].data.Add(desk[i - q,j - p]);
                        }
 
                    }
                    
                }
            int mark = 0;
            desk[x1, y1].Mark = 0;
            desk[x1, y1].Numerator(ref mark, desk[x1, y1]);
            List<Node> FullWay = new List<Node>();
            System.IO.StreamWriter sw = new System.IO.StreamWriter("horse.out");
            sw.WriteLine(desk[x2, y2].Mark);
            if (desk[x2, y2].Mark != -1)
            {
                if (desk[x2, y2].Mark != 0)
                {
                    desk[x2, y2].GetWay(FullWay);
                    FullWay.Reverse();
 
                    foreach (Node n in FullWay)
                    {
                        sw.Write(n.x + 1);
                        sw.Write(" ");
                        sw.Write(n.y + 1);
                        sw.Write(" ");
                    }
                }
                sw.Write(desk[x2, y2].x + 1);
                sw.Write(" ");
                sw.Write(desk[x2, y2].y + 1);
                sw.Write(" ");
 
            }
            sw.Close();
 
 
        }
    }
}
Работает не не проходит по времени.
Создаю в памяти граф с узлами Node, потом делаю его обход начиная с узла x1,y1. Проблема со скоростью связана с C# или у меня не оптимальный алгоритм?
1
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.01.2015, 12:10
Ответы с готовыми решениями:

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового...

Поиск кратчайшего пути в лабиринте
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки...

АСтар поиск кратчайшего пути
Здравствуйте знаю что подобных тем сотни, но я никак не могу разобраться в двух вещах. Я пытаюсь...

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

Поиск кратчайшего пути в лабиринте
Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в...

5
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,860
Завершенные тесты: 3
27.01.2015, 13:03 2
Цитата Сообщение от CAXOPOK Посмотреть сообщение
Проблема со скоростью связана с C# или у меня не оптимальный алгоритм?
скорее второе. почему б вместа дерева волну по доске не прогнать?
0
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
27.01.2015, 13:06  [ТС] 3
Поясните, как этот метод называется

Добавлено через 1 минуту
Да там даже не дерево, а граф выходит
0
pycture
1183 / 575 / 86
Регистрация: 20.09.2012
Сообщений: 1,860
Завершенные тесты: 3
27.01.2015, 13:15 4
Лучший ответ Сообщение было отмечено CAXOPOK как решение

Решение

так и называется. волновой алгоритм
1
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
27.01.2015, 13:31 5
Используй BFS и поле-массив. А то что-то много кода и разбираться не хочется.

При таких ограничениях шарп не может быть причиной. Ну если вердикт не "программа ничего не делала и была прервана" (не надо было extension-метод писать).
1
CAXOPOK
1 / 1 / 0
Регистрация: 29.03.2013
Сообщений: 59
27.01.2015, 14:51  [ТС] 6
Вообще-то, если я ничего не напутал, то в моём первом решении как раз-таки реализован обход в ширину, но он не проходит по времени.
Что касается волнового алгоритма, то я его нашёл, понял и успешно реализовал.
Выкладываю код здесь, может кому пригодится. Всем спасибо.
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Horse
{
 
 
 
    class Program
    {
        static void Main(string[] args)
        {
            System.IO.StreamReader file = new System.IO.StreamReader(@"horse.in");
            string[] arr = file.ReadLine().Split(' ');
            int M, N, p, q, x1, y1, x2, y2;
            M = int.Parse(arr[0]);
            N = int.Parse(arr[1]);
 
            p = int.Parse(arr[2]);
            q = int.Parse(arr[3]);
            x1 = int.Parse(arr[4]);
            x1--;
            y1 = int.Parse(arr[5]);
            y1--;
            x2 = int.Parse(arr[6]);
            x2--;
            y2 = int.Parse(arr[7]);
            y2--;
            int tmp = 8;
            if (p == q) tmp = 4;
            int[,] desk = new int[M, N];
            for (int i = 0; i < M; i++)
                for (int j = 0; j < N; j++)
                    desk[i, j] = -1;
            int d = 0;
            desk[x1, y1] = d;
            int[] dx = { p, -p, p, -p, q, q, -q, -q };   // смещения, соответствующие соседям ячейки
            int[] dy = { q, q, -q, -q, p, -p, p, -p };   // справа, снизу, слева и сверху
            int x, y, k;
 
            bool stop = false;
            do
            {
                stop = true;
                for (int i = 0; i < M; i++)
                    for (int j = 0; j < N; j++)
                    {
                        if (desk[i, j] == d)
                        {
                            for (k = 0; k < tmp; ++k)
                                if (i + dx[k] < M && i + dx[k] >= 0 && j + dy[k] >= 0 && j + dy[k] < N)
                                {
                                    if (desk[i + dx[k], j + dy[k]] == -1)
                                    {
                                        stop = false;
                                        desk[i + dx[k], j + dy[k]] = d + 1;
                                    }
                                }
 
 
                        }
 
 
                    }
                d++;
            } while (!stop && desk[x2, y2] == -1);
            System.IO.StreamWriter fout = new System.IO.StreamWriter(@"horse.out");
            fout.WriteLine(desk[x2, y2]);
 
            if (desk[x2, y2] != -1)
            {
                int[] px = new int[d + 1];
                int[] py = new int[d + 1];
                int len = desk[x2, y2];            
                x = x2;
                y = y2;
                d = len;
                while (d > 0)
                {
                    px[d] = x;
                    py[d] = y;
                    d--;
 
                    for (k = 0; k < tmp; ++k)
                        try
                        {
                            if (desk[x + dx[k], y + dy[k]] == d)
                            {
                                x = x + dx[k];
                                y = y + dy[k];
                                break;
                            }
                        }
                        catch (Exception) { ;}
                }
                px[0] = x1;
                py[0] = y1;
                for (int i = 0; i < len + 1; i++)
                {
                    fout.Write(px[i] + 1);
                    fout.Write(" ");
                    fout.Write(py[i] + 1);
                    fout.WriteLine(" ");
 
                }
 
            }
 
            fout.Close();
        }
    }
}
0
27.01.2015, 14:51
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.01.2015, 14:51

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов 24 минуты помогите...

Поиск кратчайшего пути в матрице или установка факта, что такового не существует
Всем привет!!!я начал решать задачку и у меня не получается, а не получается у меня самое главное...

Алгоритмы кратчайшего пути
Нужен алгоритм нахождения кратчайшего пути между двумя точками (волновой не подходит). Заранее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.