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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
Xibrand
1 / 1 / 0
Регистрация: 26.10.2011
Сообщений: 31
#1

Волновой алгоритм (шахматы, конь) - C++

01.05.2012, 19:24. Просмотров 1373. Ответов 1
Метки нет (Все метки)

Всем привет!

Пытался написать волновой алгоритм для нахождения кратчайшего пути коня на шахматной доски из A->B.

Но что-то у меня пути некорректно рисует.



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
#include<iostream>
using namespace std;
 
int i, j;
int empty = -1;
 
void print_board(int **board, int n, int m);
void horse_step(int **board, int n, int m, int start, int startY, int startX);
 
int main() {
    int n, m;
    int startX, startY, endX, endY;
    int start = 0;
    int end = -2;
 
    cout << "Size of the chessboard\n";
    cin >> n >> m;
    
    cout << "StartX, StartY\n";
    cin >> startX >> startY;
 
    cout << "EndX, EndY\n";
    cin >> endX >> endY;
 
    int **board = new int *[n];
    for(i=0; i<n; i++) {
        board[i] = new int [m];
    }
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) {
            board[i][j] = empty;
        }   
    }
    startY--;startX--;endX--;endY--;
 
    board[startY][startX] = start;
    board[endY][endX] = end;
    
    print_board(board, n, m);
    
    int temp;
    while(board[endY][endX] == end) {
        temp = start+1;
        for(i=0; i<n; i++) {
            for(j=0; j<m; j++) {
                if(board[i][j] == start) {
                    horse_step(board, n, m, temp, i, j);
                    cout << "StartY - " << i << " StartX - " << j << " Start" << start << endl;
                    print_board(board, n, m);
                }
            }
        }
        
        start++;
    }
 
 
    for(i=0; i<n; i++) {
        delete board[i];
    }
    delete []board;
    return 0;
}
 
void print_board(int **board, int n, int m) {
    for(i=0; i<n; i++) {
        for(j=0; j<m; j++) {
            cout << board[i][j] << "  ";
        }   
        cout << endl;
    }
}
 
void horse_step(int **board, int n, int m, int start, int startY, int startX) {
    if((startY-2 >= 0) && (startX-1 >= 0) && board[startY-2][startX-1] >= empty) 
        board[startY-2][startX-1] = start;
 
    if((startY-2 >= 0) && (startX+1 < m) && board[startY-2][startX+1] <= empty)
        board[startY-2][startX+1] = start;
 
    if((startY+2 < n) && (startX-1 >= 0) && board[startY+2][startX-1] <= empty)
        board[startY+2][startX-1] = start;
 
    if((startY+2 < n) && (startX+1 < m) && board[startY+2][startX+1] <= empty)
        board[startY+2][startX+1] = start;
 
 
    if((startY-1 >= 0) && (startX-2 >= 0) && board[startY-1][startX-2] <= empty)
        board[startY-1][startX-2] = start;
 
    if((startY+1 < n) && (startX-2 >= 0) && board[startY+1][startX-2] <= empty)
        board[startY+1][startX-2] = start;
 
    if((startY-1 >= 0) && (startX+2 < m) && board[startY-1][startX+2] <= empty)
        board[startY-1][startX+2] = start;
    
    if((startY+1 < n) && (startX+2 < m) && board[startY+1][startX+2] <= empty)
        board[startY+1][startX+2] = start;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.05.2012, 19:24     Волновой алгоритм (шахматы, конь)
Посмотрите здесь:

C++ Волновой алгоритм
C++ Волновой алгоритм
Волновой алгоритм поиска пути C++
C++ Шахматы, конь
Волновой или А* или Алгоритм ЛИ C++
Волновой алгоритм для двумерной матрицы C++
C++ Волновой алгоритм
Волновой алгоритм C++
C++ Волновой алгоритм - поиск минимального пути
C++ Волновой алгоритм
C++ Лабиринт - волновой алгоритм
Tiled Map и волновой алгоритм C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Xibrand
1 / 1 / 0
Регистрация: 26.10.2011
Сообщений: 31
02.05.2012, 22:32  [ТС]     Волновой алгоритм (шахматы, конь) #2
[РЕШЕНО]
Yandex
Объявления
02.05.2012, 22:32     Волновой алгоритм (шахматы, конь)
Ответ Создать тему
Опции темы

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