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

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

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

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

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

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

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

Расстояние между двумя произвольно заданными на плоскости отрезками C++
Ходы шахматного коня C++
C++ Вычисление расстояния между двумя точками, заданными на плоскости их координатами
Вычислить разницу в днях между двумя заданными датами C++
C++ Вывод всех чисел, находящихся между двумя заданными числами
Найти все пути между двумя любыми вершинами в графе C++
C++ Сколько клеток находится под боем шахматного коня
Найти вероятность существования пути в графе между заданными точками C++
C++ Функция вычисления расстояния между двумя заданными пунктами
C++ Путь шахматного коня из одного угла доски в другой за заданное кол-во шагов
C++ Зача про шахматного коня (решить, используя массив)
C++ Найти кратчайшие пути между двумя заданными точками графа

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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);
}
Yandex
Объявления
07.01.2014, 21:33     Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей
Ответ Создать тему
Опции темы

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