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

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

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

Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей - C++

07.01.2014, 13:23. Просмотров 420. Ответов 1
Метки нет (Все метки)

Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей.
ПОМОГИТЕЕЕЕ если кто напишет код прокоментите плиз

Добавлено через 6 часов 16 минут
ну пжста помогите)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2014, 13:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей (C++):

Найти кратчайшие пути между двумя заданными точками графа - C++
Добрый вечер. Кто сможет написать программу для задачи, буду очень признателен 4) Найти кратчайшие пути из точки D1 в точку D8 Вот...

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

Найти вероятность существования пути в графе между заданными точками - C++
Запутался в рекурсии. Смысл задачи: найти вероятность существования пути в графе между заданными точками. Смысл функции gen() на данном...

Ходы шахматного коня - C++
Задача заключается в том, чтобы найти минимальное количество ходов для перехода шахматного коня с клетки T1 на клетку T2. Если у кого-то...

Сколько клеток находится под боем шахматного коня - C++
есть задача. http://acm.timus.ru/problem.aspx?space=1&num=1197 написал решение: #include <iostream> using namespace std; int...

Зача про шахматного коня (решить, используя массив) - C++
Помогите пожалуйста решить задачу, на через массив: На шахматной доске NxN в клетке (x1,y1) стоит голодный шахматный конь. Он хочет...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
07.01.2014, 21:33 #2
Алгоритм не работает когда начальная точка равна конечной.
Как работает алгоритм: у коня есть 8 возможных перемешений, мы запускаем рек. функцию Check() с начальной позиции, а потом с позиции на которую передвинули коня. Если доходим до финальной точки, то распечатываем путь (путь сохраняется в векторе path). Если же попадаем в ситуацию когда некуда поставить коня- возвращаемся на шаг назад(удаляем из вектора path последниы элемент) и пробуем другие варианты.
'o'- поле в котором мы уже побывали
'x'- конечная точка
0- поле в котором мы еще не были.
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
89
90
91
92
93
94
95
96
97
#include <vector>
#include <iostream>
#include <utility>
using namespace std;
 
//checks path for same coordinates
bool Array_check(vector<pair<int, int>>& vec)
{
    for (int i = 0; i < vec.size(); i++)
    {
        for (int j = 0; j < vec.size(); j++)
        {
            if (i != j && vec[i].first == vec[j].first && vec[i].second == vec[j].second) return false;
        }
    }
    return true;
}
 
 
//Checks if i and j are in the range of the chess board
bool isValid(int i, int j)
{
    return i >= 0 && i < 8 && j >= 0 && j < 8;
}
 
void Check(vector<vector<char>>& board,vector<pair<int,int>>& path, int i, int j)
{
    path.push_back(pair<int, int>{i, j});// saves a path
    if (board[i][j] == 'x')
    {
        //prints a path
        for (pair<int,int>p:path)
        {
            cout << "(" << p.first << "," << p.second << ")";
        }
        cout << ";"<< endl;
    }
    else
    {
        board[i][j] = 'o';
        int _i, _j;
        
        if (_i = i - 2, _j = j + 1, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i - 1, _j = j + 2, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        
        if (_i = i + 2, _j = j + 1, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i + 2, _j = j - 1, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i + 1, _j = j + 2, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i + 1, _j = j - 2, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i - 1, _j = j - 2, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        if (_i = i - 2, _j = j - 1, isValid(_i, _j) && board[_i][_j] != 'o')
        {
            Check(board, path, _i, _j);
        }
        board[i][j] = 0;
    }
    //removes last place    
    path.pop_back();
}
 
int main()
{
    vector<vector<char>>board(8, vector<char>(8, 0) );
    vector<pair<int, int>>path;
    int i, j, x, y;
    cout << "Start location: i= ";
    cin >> i;
    cout << "j= ";
    cin >> j;
    cout << "Finish location: x= ";
    cin >> x;
    cout << "y= ";
    cin >> y;
    board[x][y] = 'x';
    Check(board, path, i, j);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2014, 21:33
Привет! Вот еще темы с ответами:

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

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

Функция вычисления расстояния между двумя заданными пунктами - C++
Вот задание: Представить автотрассу в виде двунаправленного списка, элементы которого содержат информацию о названии населенных пунктов и...

Вычислить расстояние между двумя точками с заданными координатами - C++
Вычислить расстояние между двумя точками с заданными координатами:A(a,d),B(u,m).


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

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

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