Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
1

Восстановление предков обхода в ширину

16.01.2014, 15:32. Просмотров 1210. Ответов 3
Метки нет (Все метки)

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Формат входных данных
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

Формат выходных данных
В первой строке выведите единственное число K - наименьшее необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа - координаты очередной клетки в пути коня.

вот мой код(палками в код не тыкать, лаптями не бросаться, кричать и брызгать слюной не надо, сам знаю, что криво):
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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
bool used[21][21];
int n, x1, y3, x2, y2, n1 = 0;
    queue<int> cht;
    queue<int> x;
    queue<int> y;
void bfs();
int main()
{
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            used[i][j] = false;
    cin >> n;
    cin >> x1 >> y3;
    cin >> x2 >> y2;
    if (x1 == x2 && y3 == y2)
    {
        cout << "0" << endl;
        cout << x1 << " " << y3;
        return 0;
    }
    bfs();
    cout << n1;
    return 0;
}
void vpk(int v1, int v2, int v3)
{
        if (v1 - 2 > 0 && v2 - 1 > 0)
        {
            x.push(v1 - 2);     y.push(v2 - 1); cht.push(v3);
        }
        if (v1 - 2 < n && v2 + 1 < n)
        {
            x.push(v1 - 2);     y.push(v2 + 1);  cht.push(v3);
        }
        if (v1 + 2 < n && v2 + 1 < n)
        {
            x.push(v1 + 2);     y.push(v2 + 1);  cht.push(v3);
        }
        if (v1 + 2 < n && v2 - 1 > 0)
        {
            x.push(v1 + 2);     y.push(v2 - 1);  cht.push(v3);
        }
        if (v1 + 1 < n && v2 + 2 < n)
        {
            x.push(v1 + 1);     y.push(v2 + 2);  cht.push(v3);
        }
        if (v1 - 1 > 0 && v2 - 2 > 0)
        {
            x.push(v1 - 1);     y.push(v2 - 2);  cht.push(v3);
        }
        if (v1 - 1 > 0 && v2 + 2 < n)
        {
            x.push(v1 - 1);     y.push(v2 + 2);  cht.push(v3);
        }
        if (v1 + 1 < n && v2 - 2 > 0)
        {
            x.push(v1 + 1);     y.push(v2 - 2);  cht.push(v3);
        }
}
void bfs()
{
    cht.push(n1);
    x.push(x1);
    y.push(y3);
    while(!x.empty() && !y.empty())
    {
        int v1 = x.front();
        x.pop();
        int v2 = y.front();
        y.pop();
        int v3 = cht.front();
        cht.pop();
        if(used[v1][v2])
            continue;
        used [v1][v2] = true;
        v3 = v3 + 1;
        if((v1 - 2 == x2 && v2 - 1 == y2) || (v1 + 2 == x2 && v2 + 1 == y2) || (v1 - 2 == x2 && v2 + 1 == y2) || (v1 + 2 == x2 && v2 - 1 == y2) || (v1 - 1 == x2 && v2 - 2 == y2) || (v1 + 1 == x2 && v2 + 2 == y2) || (v1 + 1 == x2 && v2 - 2 == y2) || (v1 - 1 == x2 || v2 + 2 == y2))
        {
            n1 = v3;
            break;
        }
        vpk(v1,v2,v3);
    }
}
Вот как сюда восстановление пути впихнуть, чтобы предков прописать?
Будет круто, если вы мне дадите не код, а объясните, как тут это сделать, чтобы я сам до всего дошел. Ну а если не получится, код скините.
Помогите пожалуйста.
З.Ы. Если можно как-нибудь оптимизировать, покажите, а то интересно, как умно можно было написать.

Добавлено через 42 минуты
UP.

Добавлено через 21 минуту
ну ааааап. =(

Добавлено через 15 часов 50 минут
=((

Добавлено через 2 часа 3 минуты
что, у всех труба чтоле?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2014, 15:32
Ответы с готовыми решениями:

Реализация обхода в ширину и глубину бинарного дерева
Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим...

Порядок инициализации предков
class A {...}; class B {...}; class C : A,B { private: int Var; public: C(const int...

Найти всех предков человека с номером p
заданы n человек и два массива натуральных чисел mother и father, такие, что mother – номер матери...

Алгоритмы поиска кратчайших путей в ширину и двунаправленный в ширину
Реализовать алгоритм поиска кратчайшего пути. Двунаправленный поиск в ширину. Вот есть 2...

Определить предикат предок и найти всех предков и предков конкретного лица
ОЧЕНЬ нужна помощь! Задача такая: Определить предикат предок и найти всех предков и предков...

3
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
16.01.2014, 16:07 2
традиционно заводим массив предков p[i][j] - клетка, из которой мы попали в клетку с координатами (i; j). очевидно, при bfs у каждой клетки может быть только один предок, так что все ок.
считается хорошей практикой в таких задачах (шахматных, например) ввиду того, что перемещения при обходах имеют нетривиальный характер (например, ход коня) заводить еще массив указателей на функции, которые будут осуществлять тот или иной ход.
восстановление ответа выглядит просто. например, как мы попали из (1; 1) в (i; j):
C++
1
2
3
4
5
6
p[1][1] = (-1; -1);
int ni = i, nj = j;
while(ni != -1 || nj != -1) {
   cout << (ni; nj) << endl;
   (ni; nj) <-- p[ni][nj];
}
0
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
16.01.2014, 17:22  [ТС] 3
Цитата Сообщение от salam Посмотреть сообщение
традиционно заводим массив предков p[i][j] - клетка, из которой мы попали в клетку с координатами (i; j). очевидно, при bfs у каждой клетки может быть только один предок, так что все ок.
считается хорошей практикой в таких задачах (шахматных, например) ввиду того, что перемещения при обходах имеют нетривиальный характер (например, ход коня) заводить еще массив указателей на функции, которые будут осуществлять тот или иной ход.
восстановление ответа выглядит просто. например, как мы попали из (1; 1) в (i; j):
C++
1
2
3
4
5
6
p[1][1] = (-1; -1);
int ni = i, nj = j;
while(ni != -1 || nj != -1) {
   cout << (ni; nj) << endl;
   (ni; nj) <-- p[ni][nj];
}
C++
1
int ni = i, nj = j;
Что такое i и j.
C++
1
   cout << (ni; nj) << endl;
это ты что выводишь
C++
1
(ni; nj) <-- p[ni][nj];
что здесь происходит
C++
1
p[1][1] = (-1; -1);
и это какой вид данных, что такое заполнение.
0
Wiiiiijjj
18 / 18 / 18
Регистрация: 25.08.2014
Сообщений: 186
08.11.2014, 23:55 4
Ап, помогите решить, пожалуйста
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2014, 23:55

Алгоритм обхода графов в ширину
Написать программу на языке Паскаль алгоритма обхода графов в ширину и описание если не трудно

Реализация обхода графа в ширину
Здравствуйте, помогите пожалуйста перевести словесное описание на программный код

Программа обхода графа в ширину и глубину.
Уважаемые программисты. Нужно помощь. Необходим код программы(Delphi) которая построит древовидный...


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

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

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