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

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

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

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

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

помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2013, 18:21
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Кратчайший путь коня с++ (C++):

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

Кратчайший путь в графе. - C++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

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

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

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

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

12
Ternsip
662 / 190 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 18:41 #2
virus945, какие ограничения по времени и памяти, и какой max размер доски ?

Добавлено через 1 минуту
virus945, решается через bfs, если время жмёт, можно прекальк сделать
0
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 18:48  [ТС] #3
Ternsip, ну веремени меньше недели как бы осталось, уже не знаю куда податься
0
dr.curse
392 / 348 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.05.2013, 18:50 #4
Цитата Сообщение от Ternsip Посмотреть сообщение
если время жмёт, можно прекальк сделать
а какой прекальк?
0
Ternsip
662 / 190 / 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;
}
0
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 19:03  [ТС] #6
Ternsip, вы запускали этот код?)
0
Ternsip
662 / 190 / 6
Регистрация: 10.05.2012
Сообщений: 595
23.05.2013, 19:05 #7
aram_gyumri, ответы для всех возможных вхыодных n, A, B

Добавлено через 15 секунд
virus945, я его только что написал и протестировал, да. Возможно вы не заметили freopen, это перегразка на файловый ввод-вывод
0
dr.curse
392 / 348 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
23.05.2013, 19:12 #8
Цитата Сообщение от Ternsip Посмотреть сообщение
aram_gyumri, ответы для всех возможных вхыодных n, A, B
это то я понимаю, но если бфс не зайдет по времени то прекальк уж точно не зайдето по памяти
0
Ternsip
662 / 190 / 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;
}
0
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
23.05.2013, 19:38  [ТС] #10
еще варианты будут?
0
Kuzia domovenok
2125 / 1955 / 194
Регистрация: 25.03.2012
Сообщений: 6,806
Записей в блоге: 1
23.05.2013, 19:43 #11
Какие проблемы с программой Ternsipа?
0
virus945
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
24.05.2013, 08:55  [ТС] #12
Kuzia domovenok, я низнаю на чем он писал, но у меня при компиляции куча ошибок выдает
0
Kuzia domovenok
2125 / 1955 / 194
Регистрация: 25.03.2012
Сообщений: 6,806
Записей в блоге: 1
25.05.2013, 05:30 #13
какие ошибки? приведи список.
какая IDE?
В MSVS всё собирается и запускается.
Конечно, возможны рантайм-ошибки...
но ведь ты говоришь, что у тебя не компилирует?
0
25.05.2013, 05:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2013, 05:30
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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