Форум программистов, компьютерный форум 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++ Динамическая память, проблемы с освобождением Всем привет! Проблема стара как этот мир, но есть некая отличительная черта по которой я создал эту тему. Задача следующая. Создаю файл и кидаю в него строку, закрываю файл. Далее открываю этот... подробнее

Показать сообщение отдельно
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,386
Завершенные тесты: 1
03.04.2012, 02:44
Делал как то тоже, относительно недавно, в прошлом году. По заданию из Дейтелов. Вот что получилось ( там по заданию если попадались из текущих возможных ходы с одинаковыми числами доступности, то нужно проверять на 1 ход вперед, какой предпочесть ), вдруг поможет, размер доски можно в принципе любой ( естественно не отрицательный ), массив доступности сам подстраивается:
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
148
149
150
151
152
153
#include <iostream>
#include <iomanip>
 
std::size_t digitsInNumber( int number ) {
    int digits = 1;
 
    while ( number /= 10 )
        digits++;
 
    return digits;
}
 
void arrayOutput( const int* const *const array, const int size ) {
    std::size_t w = digitsInNumber( size * size );
 
    for ( int i = 0; i < size; i++ ) {
        for ( int j = 0; j < size; j++ )
            std::cout << std::setw( w ) << array[ i ][ j ] << ' ';
 
        std::cout << std::endl;
    }
}
 
void resetBoard( int **b, const int size ) {
    for ( int i = 0; i < size; i++ )
        for ( int j = 0; j < size; j++ )
            b[ i ][ j ] = 0;
}
 
void resetAccessibility( int **a, const int boardSize, const int vertical[], const int horizontal[], const int movesSize ) {
    resetBoard( a, boardSize );
 
    for ( int i = 0; i < boardSize; i++ ) {
        for ( int j = 0; j < boardSize; j++ )
            for ( int k = 0; k < movesSize; k++ )
                if ( i + vertical[ k ] >= 0 && i + vertical[ k ] < boardSize && j + horizontal[ k ] >= 0 && j + horizontal[ k ] < boardSize )
                    a[ i + vertical[ k ]][ j + horizontal[ k ]]++;
    }
}
 
int **initMatrix( const int size ) {
    int** tmpArr = new int*[ size ];
 
    for ( int i = 0; i < size; i++ ) {
        tmpArr[ i ] = new int[ size ];
 
        for ( int j = 0; j < size; j++ )
            tmpArr[ i ][ j ] = 0;
    }
 
    return tmpArr;
}
 
bool moveIsPosible( const int posX, const int posY, int **board, const int size ) {
    return ( posX >= 0 && posX < size && posY >= 0 && posY < size && board[ posX ][ posY ] == 0 );
}
 
int main() {
    const int sizeOfBoard = 8,
              sizeOfMoves = 8;
 
    const int vertical[ sizeOfMoves ] = { -1, -2, -2, -1, 1, 2, 2, 1 },
              horizontal[ sizeOfMoves ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
 
    int **board = initMatrix( sizeOfBoard ),
        **accessibility = initMatrix( sizeOfBoard );
 
    int currentRow = 0,
        currentColumn = 0,
        moveNumber = 0,
        move = 0,
        completeJourneys = 0;
 
    for ( int row = 0; row < sizeOfBoard; row++ ) {
        for ( int col = 0; col < sizeOfBoard; col++ ) {
            resetBoard( board, sizeOfBoard );
            resetAccessibility( accessibility, sizeOfBoard, vertical, horizontal, sizeOfMoves );
 
            currentRow = row;
            currentColumn = col;
            board[ currentRow ][ currentColumn ] = move = 1;
 
            do {
                for ( int k = 0; k < sizeOfMoves; k++ ) {
                    if ( currentRow + vertical[ k ] >= 0 && currentRow + vertical[ k ] < sizeOfBoard && currentColumn + horizontal[ k ] >= 0 && currentColumn + horizontal[ k ] < sizeOfBoard )
                        accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]]--;
                }
 
                moveNumber = -1;
 
                for ( int k = 0; k < sizeOfMoves; k++ ) {
                    if ( moveIsPosible( currentRow + vertical[ k ], currentColumn + horizontal[ k ], board, sizeOfBoard )) {
                        if ( moveNumber == -1 )
                            moveNumber = k;
                        else if ( accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]] < accessibility[ currentRow + vertical[ moveNumber ]][ currentColumn + horizontal[ moveNumber ]])
                            moveNumber = k;
                        else if ( accessibility[ currentRow + vertical[ k ]][ currentColumn + horizontal[ k ]] == accessibility[ currentRow + vertical[ moveNumber ]][ currentColumn + horizontal[ moveNumber ]]) {
                            int tmpMoveNumber1 = -1,
                                tmpRowPos1 = currentRow + vertical[ moveNumber ],
                                tmpColPos1 = currentColumn + horizontal[ moveNumber ],
                                tmpMoveNumber2 = -1,
                                tmpRowPos2 = currentRow + vertical[ k ],
                                tmpColPos2 = currentColumn + horizontal[ k ];
 
                            for ( int n = 0; n < sizeOfMoves; n++ ) {
                                if ( moveIsPosible( tmpRowPos1 + vertical[ n ], tmpColPos1 + horizontal[ n ], board, sizeOfBoard )) {
                                    if ( tmpMoveNumber1 == -1 )
                                        tmpMoveNumber1 = n;
                                    else if ( accessibility[ tmpRowPos1 + vertical[ n ]][ tmpColPos1 + horizontal[ n ]] < accessibility[ tmpRowPos1 + vertical[ tmpMoveNumber1 ]][ tmpColPos1 + horizontal[ tmpMoveNumber1 ]])
                                        tmpMoveNumber1 = n;
                                }
 
                                if ( moveIsPosible( tmpRowPos2 + vertical[ n ], tmpColPos2 + horizontal[ n ], board, sizeOfBoard )) {
                                    if ( tmpMoveNumber2 == -1 )
                                        tmpMoveNumber2 = n;
                                    else if ( accessibility[ tmpRowPos2 + vertical[ n ]][ tmpColPos2 + horizontal[ n ]] < accessibility[ tmpRowPos2 + vertical[ tmpMoveNumber2 ]][ tmpColPos2 + horizontal[ tmpMoveNumber2 ]])
                                        tmpMoveNumber2 = n;
                                }
                            }
 
                            if (( tmpMoveNumber1 == -1 && tmpMoveNumber2 != -1 )
                                || (( tmpMoveNumber1 != -1 && tmpMoveNumber2 != -1 )
                                     && ( accessibility[ tmpRowPos2 + vertical[ tmpMoveNumber2 ]][ tmpColPos2 + horizontal[ tmpMoveNumber2 ]] < accessibility[ tmpRowPos1 + vertical[ tmpMoveNumber1 ]][ tmpColPos1 + horizontal[ tmpMoveNumber1 ]])))
                                moveNumber = k;
                        }
                    }
                }
 
                if ( moveNumber != -1 ) {
                    currentRow += vertical[ moveNumber ];
                    currentColumn += horizontal[ moveNumber ];
                    board[ currentRow ][ currentColumn ] = ++move;
                }
 
            } while ( moveNumber != -1 );
 
            if ( move == sizeOfBoard * sizeOfBoard )
                completeJourneys++;
        }
    }
 
    for ( int i = 0; i < sizeOfBoard; i++ ) {
        delete [] board[ i ];
        delete [] accessibility[ i ];
    }
 
    delete [] board;
    delete [] accessibility;
 
    std::cout << "Size of board: " << sizeOfBoard << " * " << sizeOfBoard << "\nComplete journeys: " << completeJourneys << " of " << sizeOfBoard * sizeOfBoard << std::endl;
 
    return 0;
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru