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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
#1

Кратчайший путь коня с++ - C++

23.05.2013, 18:21. Просмотров 2353. Ответов 12
Метки нет (Все метки)

помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 18:21     Кратчайший путь коня с++
Посмотрите здесь:

Графы кратчайший путь ! - C++
Помогите написать функцию для поиска кратчайшего пути между вершинами которые задаются с клавы я написал правда получилось что это...

Найдите кратчайший путь в графе - C++
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите кратчайший путь в графе, используя...

Кратчайший путь в графе(Рекурсия) - C++
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под...

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти кратчайший путь шахматного короля - C++
Здравствуйте, имеется задача: Есть шахматное поле NxM N, M ≤ 10^9 На шахматном поле отмечено два прямоугольника размерами не менее...

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Графы, расположить людей по билетам, кратчайший путь - C++
Здравствуйте. На соревнованиях codeforces я часто замечаю, что больше половины задач на тему графов, где нужно находить кратчайший путь или...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 18:41     Кратчайший путь коня с++ #2
virus945, какие ограничения по времени и памяти, и какой max размер доски ?

Добавлено через 1 минуту
virus945, решается через bfs, если время жмёт, можно прекальк сделать
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 18:48  [ТС]     Кратчайший путь коня с++ #3
Ternsip, ну веремени меньше недели как бы осталось, уже не знаю куда податься
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.05.2013, 18:50     Кратчайший путь коня с++ #4
Цитата Сообщение от Ternsip Посмотреть сообщение
если время жмёт, можно прекальк сделать
а какой прекальк?
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 19:01     Кратчайший путь коня с++ #5
virus945, таблица нумеруется от 0 до n-1, сначала вводится n - раземр доски
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
#include <iostream>
#include <vector>
#include <limits>
#include <string>
#include <algorithm>
#include <queue>
 
using namespace std;
 
 
int main(){    
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    cin >> n;
    int x[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int y[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    queue <pair<int, int> > q;
    pair <int, int> start, end, temp, nan = make_pair(-1, -1);
    vector <vector <pair<int, int> > > p(n, vector <pair<int, int>> (n, nan));
    cin >> start.first >> start.second >> end.first >> end.second;
    q.push(start);
    p[start.first][start.second] = start;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == end) {
            cout << "The way is : \n";
            vector <pair <int, int> > way;
            while (temp != start) {
                way.push_back(temp);
                temp = p[temp.first][temp.second];
            }
            way.push_back(start);
            for (int i = way.size() - 1; i >= 0; i--) {
                cout << way[i].first << " " << way[i].second << endl;
            }
            return 0;
        }
        for (int i = 0; i < 8; i++) {
            int nx = temp.first + x[i];
            int ny = temp.second + y[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && p[nx][ny] == nan) {
                p[nx][ny] = temp;
                q.push(make_pair(nx, ny));
            }
        }
    }
    cout << "No way";
    return 0;
}
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 19:03  [ТС]     Кратчайший путь коня с++ #6
Ternsip, вы запускали этот код?)
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 19:05     Кратчайший путь коня с++ #7
aram_gyumri, ответы для всех возможных вхыодных n, A, B

Добавлено через 15 секунд
virus945, я его только что написал и протестировал, да. Возможно вы не заметили freopen, это перегразка на файловый ввод-вывод
dr.curse
387 / 343 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.05.2013, 19:12     Кратчайший путь коня с++ #8
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, ответы для всех возможных вхыодных n, A, B
это то я понимаю, но если бфс не зайдет по времени то прекальк уж точно не зайдето по памяти
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 19:22     Кратчайший путь коня с++ #9
virus945,
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
#include <iostream>
#include <vector>
#include <limits>
#include <string>
#include <algorithm>
#include <queue>
 
int main(){    
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n;
    std::cin >> n;
    int x[8] = {1, 1, -1, -1, 2, 2, -2, -2};
    int y[8] = {2, -2, 2, -2, 1, -1, 1, -1};
    std::queue <std::pair<int, int> > q;
    std::pair <int, int> start, end, temp, nan = std::make_pair(-1, -1);
    std::vector <std::vector <std::pair<int, int> > > p(n, std::vector <std::pair<int, int> > (n, nan));
    std::cin >> start.first >> start.second >> end.first >> end.second;
    q.push(start);
    p[start.first][start.second] = start;
    while (!q.empty()) {
        temp = q.front();
        q.pop();
        if (temp == end) {
            std::cout << "The way is : \n";
            std::vector <std::pair <int, int> > way;
            while (temp != start) {
                way.push_back(temp);
                temp = p[temp.first][temp.second];
            }
            way.push_back(start);
            for (int i = way.size() - 1; i >= 0; i--) {
                std::cout << way[i].first << " " << way[i].second << std::endl;
            }
            return 0;
        }
        for (int i = 0; i < 8; i++) {
            int nx = temp.first + x[i];
            int ny = temp.second + y[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && p[nx][ny] == nan) {
                p[nx][ny] = temp;
                q.push(std::make_pair(nx, ny));
            }
        }
    }
    std::cout << "No way";
    return 0;
}
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 19:38  [ТС]     Кратчайший путь коня с++ #10
еще варианты будут?
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
23.05.2013, 19:43     Кратчайший путь коня с++ #11
Какие проблемы с программой Ternsipа?
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
24.05.2013, 08:55  [ТС]     Кратчайший путь коня с++ #12
Kuzia domovenok, я низнаю на чем он писал, но у меня при компиляции куча ошибок выдает
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2013, 05:30     Кратчайший путь коня с++
Еще ссылки по теме:

Кратчайший путь до какой-то координаты. Ошибка std::bad_alloc - C++
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная...

Обогнуть остров, выбрав кратчайший путь вокруг острова - C++
Во входном файле находятся: число N, задающее количество вершин многоугольника и далее координаты вершин многоугольника в виде списка x , y...

Путь шахматного коня из одного угла доски в другой за заданное кол-во шагов - C++
Шахматная фигура &quot;конь&quot; перемещается на одну клетку по горизонтали и на две клетки по вертикали или на две клетки по горизонтали и на одну...

С помощью метода волны найти кратчайший путь из одной клетки в другую (ход конём) - C++
Пытаюсь решить такую задачу: с помощью метода волны нужно найти кратчайший путь из одной клетки в другую. Проблема состоит в том, что я...

Найти кратчайший путь в лабиринте, который представлен в виде составного куба заданного размера - C++
Найти кратчайший путь в лабиринте, который представлен в виде составного куба NxNxN, состоящего из маленьких кубиков. Все кубики...


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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
1890 / 1745 / 118
Регистрация: 25.03.2012
Сообщений: 5,924
Записей в блоге: 1
25.05.2013, 05:30     Кратчайший путь коня с++ #13
какие ошибки? приведи список.
какая IDE?
В MSVS всё собирается и запускается.
Конечно, возможны рантайм-ошибки...
но ведь ты говоришь, что у тебя не компилирует?
Yandex
Объявления
25.05.2013, 05:30     Кратчайший путь коня с++
Ответ Создать тему
Опции темы

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