Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
16.01.2014, 15:32     Восстановление предков обхода в ширину #1
На шахматной доске 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 минуты
что, у всех труба чтоле?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2014, 15:32     Восстановление предков обхода в ширину
Посмотрите здесь:

C++ алгоритм обхода поля кубиком
Порядок инициализации предков C++
Алгоритм обхода лабиринта C++
C++ варианты обхода графа
Процедура обхода для дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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];
}
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);
и это какой вид данных, что такое заполнение.
Wiiiiijjj
 Аватар для Wiiiiijjj
17 / 17 / 6
Регистрация: 25.08.2014
Сообщений: 186
08.11.2014, 23:55     Восстановление предков обхода в ширину #4
Ап, помогите решить, пожалуйста
Yandex
Объявления
08.11.2014, 23:55     Восстановление предков обхода в ширину
Ответ Создать тему
Опции темы

Текущее время: 12:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru