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

Путешествие коня. Почему конь не хочет пробежать все возможные варианты? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Задача на создание символьного файла http://www.cyberforum.ru/cpp-beginners/thread519721.html
Дан текстовый файл. Создать символьный файл, содержащий все сим-волы, встретившиеся в тексте, включая пробел и знаки препинания (без повторений). Символы располагать в порядке их первого появления в...
C++ Кусочно-линейная аппроксимация Добрый времени суток всем. Необходима помощь в написание алгоритма кусочно-линейной аппроксимации. У меня дана таблица зависимости, грубо говоря градуировка сигнала x(Вход) и y(Выход). Например: x... http://www.cyberforum.ru/cpp-beginners/thread519713.html
Найти и вывести номера структур, содержащих числа больше заданного C++
Имеется база данных, содержащая числители и знаменатели дробных чисел. Например, последовательность чисел 5/18, 7/13, 9/8, … хранится в виде: Номер структуры 1 2 3 … Числитель 5 7 9 …...
C++ помогит пожалуйста с программой «Обработка массивов в С++»
Тема «Обработка массивов в С++» Задание: Необходимо написать и отладить программу в среде Borland C++ 3.1 по задан- ному варианту с обязательным применением массивов. В массивах вещественных...
C++ Созадать/записать в файл, из под другой учетки. http://www.cyberforum.ru/cpp-beginners/thread519673.html
Приветствую, не подскажите как произвести данную манипуляцию? Даже копать в какую сторону не знаю, была мысль создать доп. программу, запускать с помощью CreateProcessWithLogonW() и передавать ей...
C++ Динамическая память, проблемы с освобождением Всем привет! Проблема стара как этот мир, но есть некая отличительная черта по которой я создал эту тему. Задача следующая. Создаю файл и кидаю в него строку, закрываю файл. Далее открываю этот... подробнее

Показать сообщение отдельно
fasked
Эксперт С++
4937 / 2517 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.03.2012, 08:11
Что-то у меня тут было про коней, кину на всякий случай, а то все равно не понятно, что делать надо:
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <iomanip>
 
// массив всех возможных ходов фигуры (буквой Г)
const int move_types = 8;
int possible_moves[move_types][2]  = {
    {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
    {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1} 
};
 
int **desc_state;   // указатель на поле (доску)
int size_x, size_y; // размеры доски
int cur_x, cur_y;   // текущая позиция
 
int max_moves;      // максимальное количество ходов
unsigned int back_ret;
 
// определить возможно ли поставить фигуру на позицию x,y
bool position_possible(int x, int y)
{
    return x >= 0 && y >= 0 && x < size_x && y < size_y;
}
 
// определить возможно ли сделать ход на позицию x,y
// возможно если фигуру можно поставить на клетку x,y 
// и эта клетка не была пройдена ранее
bool move_possible(int x, int y) 
{
    return position_possible(x,y) && desc_state[x][y] == 0;
}
 
// рекурсивная функция поиска пути
bool find_path(int cur_x, int cur_y, int move_num)
{
    // занять клетку cur_x, cur_y
    // записать в нее номер хода
    desc_state[cur_x][cur_y] = move_num;
    
    // если номер текущего хода больше числа максимальных ходов 
    // то обход доски завершен
    if(move_num > max_moves)
        return true;
 
    // цикл проверки всех возможных ходов
    for(int i = 0; i < move_types; ++i)
    {
        int next_x = cur_x + possible_moves[i][0];
        int next_y = cur_y + possible_moves[i][1];
 
        // если возможен такой ход и следующий ход 
        // то вернуть true
        if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
            return true;
    }
 
    // этот участок кода отработает если такой ход невозможен
    // обнулить клетку и уменьшить число ходов на единицу
    desc_state[cur_x][cur_y] = 0;
    ++back_ret;
    --move_num;
 
    return false;
}
 
// начальная инициализация
void init(int **desc, int nrows, int ncols, int start_x, int start_y)
{
    desc_state = desc;  // указатель на двумерный массив - доска
    size_x = nrows;     // размеры доски
    size_y = ncols;
 
    // обнуление доски
    for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
            desc_state[i][j] = 0;
    }
 
    back_ret = 0;
 
    // количество ходов 
    max_moves = size_x * size_y - 1;
}
 
// это просто вывод доски
void output_path()
{
    for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
            std::cout << std::setfill('0') << std::setw(2) << desc_state[i][j] << ' ';
 
        std::cout << std::endl;
    }
}
 
int main() 
{
    int nrows = 0;
    int ncols = 0;
 
    int **desc = NULL;
    int sx = 0;
    int sy = 0;
 
    std::cout << "input vertical size: ";
    std::cin  >> nrows;
 
    std::cout << "input horizontal size : ";
    std::cin  >> ncols;
 
    std::cout << "input start X-position: ";
    std::cin  >> sx;
 
    std::cout << "input start Y-position: ";
    std::cin  >> sy;
 
    if(sx >= nrows || sy >= ncols) {
        std::cout << "start positions invalid" << std::endl;
        return -1;
    }
 
    // выделить память под двумерный массив (доску)
    desc = new int *[nrows];
    for(int i = 0; i < nrows; ++i) 
        desc[i] = new int[ncols];
 
    // инициализация
    init(desc, nrows, ncols, sx, sy);
 
    // если функция find_path вернет true
    // то обход существует
    // иначе не существует
    if(find_path(sx, sy, 1))
        output_path();
    else
        std::cout << "path not found" << std::endl;
 
//  std::cout << "\nback ret: " << back_ret;
//  std::cout << "\nmove num: " << move_num;
//  std::cout << std::endl;
 
    // освободить память
    for(int i = 0; i < nrows; ++i)
        delete[] desc[i];
    delete[] desc;
 
    return 0;
}
Как минимум здесь тоже перебирается все возможное количество ходов.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru