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

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

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

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

16.01.2014, 15:32. Просмотров 951. Ответов 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++
class A {...}; class B {...}; class C : A,B { private: int Var; public: C(const int &amp;v) : A(&amp;Var), B(&amp;Var) {...

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

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

Алгоритм обхода лабиринта - C++
Помогите реализовать алгоритм обхода лабиринта, на примере матрицы nxn, где 1 (единицы) это проходимые элементы, а 0 (нули) это...

Варианты обхода графа - C++
подскажите пожалуйста сколько путей существует для такого графа, чтобы проходить через каждую Добавлено через 44 секунды или...

Методы обхода графов - C++
Всем привет! Есть задание : Обойти граф, используя заданный алгоритм ( Обход в глубину по матрице инцидентности ). Все что касается...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 726
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
17 / 17 / 6
Регистрация: 25.08.2014
Сообщений: 186
08.11.2014, 23:55 #4
Ап, помогите решить, пожалуйста
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2014, 23:55
Привет! Вот еще темы с ответами:

Вывод обхода дерева в файл - C++
Есть бинарное дерево, не могу реализовать в нем вывод обхода дерева в файл из функции show(Node *&amp;der), вроде как-то можно забить данные из...

Процедура обхода для дерева - C++
Постройте процедуру обхода для получения следующей информации о деревьях - подсчитайте показатель сбалансированности для бинарного дерева...

алгоритм обхода поля кубиком - C++
народ - никому не попадалась задачка такого вида: есть поле n*n - начало в координате 0*0(верхний левый угол). есть кубик с 1 красной...

Процедура обхода для дерева - C++
постройте процедуру обхода для определения длины бинарного(или произвольного) дерева (т.е. длину максимальной ветви) PS если можно то...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.11.2014, 23:55
Ответ Создать тему
Опции темы

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