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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
#1

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

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

C++ алгоритм обхода поля кубиком
C++ Сортировка точек в порядке обхода
Порядок инициализации предков C++
C++ Реализация алгоритма обхода лабиринта
Алгоритм обхода лабиринта C++
C++ Варианты обхода графа
C++ Методы обхода графов
Процедура обхода для дерева C++
Процедура обхода для дерева C++
Найти всех предков человека с номером p 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     Восстановление предков обхода в ширину
Ответ Создать тему
Опции темы

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