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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Контейнер deque http://www.cyberforum.ru/cpp-beginners/thread1072429.html
Задание:(используя контейнер deque) ввести последовательность натуральных чисел,у конце которой 0.Не сохраняя всей последовательности в памяти, вывести порядковые номера крупнейших цифр...
C++ Каков смысл в "куче"? Всем привет! Прогуглил все вдоль и поперек, прочитал достаточно инфы, но так и не понял где, как и зачем мне может понадобиться создавать из последовательности элементов кучу... Понял что... http://www.cyberforum.ru/cpp-beginners/thread1072419.html
Разбить программу на функции C++
объясните, пожалуйста, как эту программу разбить на три функции: ввод, обработка, вывод. глобальные переменные использовать нельзя. в таком виде все работает как надо ) #include <iostream> using...
Вместо значений массива в cout выводит адреса C++
Помогите пожалуйста! Вместо значений массива в cout выводит адреса #include<iostream> #include<conio.h> #include <iomanip> #include <math.h> #include <fstream> /*void WriteComplex(char *...
C++ Вычислить площадь треугольника и вывести на экран http://www.cyberforum.ru/cpp-beginners/thread1072384.html
Директивы препроцессора и функции printf () и scanf () Спасайте товарищи,а то сессию завалю((
C++ Написать (переделать) программу с использованием ссылок в качестве параметров функций для нахождения минимального элемента из 3-х заданных Просто нахождение написал. Подскажите как использовать ссылки (&) в качестве параметров функций. #include "stdafx.h" #include "iostream" using namespace std; int _tmain(int argc, _TCHAR*... подробнее

Показать сообщение отдельно
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89

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

16.01.2014, 15:32. Просмотров 957. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru