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

Соединить шахматные 2 клетки кратчайшим путем коня - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
KeR
0 / 0 / 0
Регистрация: 05.12.2009
Сообщений: 102
17.03.2010, 14:57     Соединить шахматные 2 клетки кратчайшим путем коня #1
ребят подскажите алгоритм и через чего лучше реализовывать, желательно предлагать самые простые варианты, подскажите пожалуста потом сделаю нароботки и чую продолжу спрашивать че да как(c++)
Соединить шахматные 2 клетки кратчайшим путем коня
пример, но впроинципе можно чтоб и числами выдава, а не буквами чтоб типами хоть голову не мучать
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Грымзик
 Аватар для Грымзик
2466 / 1443 / 31
Регистрация: 14.09.2009
Сообщений: 2,742
17.03.2010, 16:58     Соединить шахматные 2 клетки кратчайшим путем коня #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Это поиск в ширину. Доска маленькая, поэтому можно совсем просто, без реализации очереди. Доска - это двумерный массив целых чисел. В начальную клетку ставишь значение 0, а в остальные например 100. На первом шаге смотришь в какие клетки можно попасть из начальных, и ставишь туда цифру 1. На втором просматриваешь всю доску, если встречается цифра 1, то смотришь куда можно пойти из нее, и если эта клетка имеет значение 100, то туда ставишь цифру 2. И так далее, пока на каком-либо шаге ты не сможешь сходить на конечную клетку. А потом надо будет вывести путь. В обратном порядке он ищется очень легко, просто из конечной клетки (пусть она имеет значение например 8) ищешь любую клетку, в которую можно из нее пойти, и которая имеет значение 7. Эта клетка будет последним шагом пути. Далее также рекурсивно ищешь предпоследний шаг пути (клетку со значением 6, в которую можно сходить из текущей клетки со значением 7).
KeR
0 / 0 / 0
Регистрация: 05.12.2009
Сообщений: 102
18.03.2010, 08:32  [ТС]     Соединить шахматные 2 клетки кратчайшим путем коня #3
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
#include <iostream>  
using namespace std;
int main()
{
    int desk[8][8] = {10}; // доска 8х8. пусть незанятые клетки будут равны 10
    int nkx, nky, kkx, kky, x, y, n;
    cout<<"Vvedite na4alnoe pologenie kon9I\n";
    cin>>nkx;
    cin>>nky;
    cout<<"Vvedite kone4noe pologenie kon9I\n";
    cin>>kkx;
    cin>>kky;
    x=nkx;
    y=nky;
    n=1;
    if (desk[x+3][y+1]==10)
    {
        desk[x+3][y+1]=n;
    }
    if (desk[x+3][y-1]==10)
    {
        desk[x+3][y-1]=n;
    }
    if (desk[x-3][y+1]==10)
    {
        desk[x-3][y+1]=n;
    }
    if (desk[x-3][y-1]==10)
    {
        desk[x-3][y-1]=n;
    }
    if (desk[x+1][y-3]==10)
    {
        desk[x+1][y-3]=n;
    }
    if (desk[x+1][y+3]==10)
    {
        desk[x+1][y+3]=n;
    }
    if (desk[x-1][y-3]==10
    {
        desk[x-1][y-3]=n;
    }
    if (desk[x-1][y+3]==10)
    {
        desk[x-1][y+3]=n;
    }
for (int i=0; i<8; i++)
{
    for(int j=0; j<8; j++)
    {
        if (desk[i][j]==1)
        {
            
        }
}
Добавлено через 2 минуты
Грымзик, спасибо, но вот в коде застопорился, вот я ищу где равно, 1 и вот как мне дальше написать чтоб он искал следующую свободную клетку?
Грымзик
 Аватар для Грымзик
2466 / 1443 / 31
Регистрация: 14.09.2009
Сообщений: 2,742
18.03.2010, 12:34     Соединить шахматные 2 клетки кратчайшим путем коня #4
У Вас много ошибок и недочетов. Нельзя было выбирать число 10, поскольку вдруг потребуется больше 10 ходов, надо заведомо недостижимое число брать. Нельзя так заполнять массив int desk[8][8] = {10}; Вы бы посмотрели что получилось при этом. И прежде, чем обращаться к элементу массива, надо проверить индексы. А еще конь делает ход длиной в 2 клетки, а не 3. Заполнения массива я написала,а вывод пути уж сами сделайте.
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
#include <iostream>  
using namespace std;
int main()
{
        int desk[8][8]; // äîñêГ* 8Гµ8. ГЇГіГ±ГІГј Г*ГҐГ§Г*Г*ÿòûå êëåòêè áóäóò Г°Г*ГўГ*Г» 10
        int nkx, nky, kkx, kky, x, y, n;
        cout<<"Vvedite na4alnoe pologenie kon9I\n";//cisla ot 1 do 8, poetomu potom umenshaem na 1
        cin>>nkx;
        cin>>nky;
        cout<<"Vvedite kone4noe pologenie kon9I\n";
        cin>>kkx;
        --kkx;
        cin>>kky;
        --kky;
        for (x=0; x<8; ++x)
            for (y=0; y<8; ++y)
                desk[x][y]=100;
        desk[nkx-1][nky-1]=0;
        for (n=1; desk[kkx][kky]==100; ++n)
            for (x=0; x<8; x++)
                for(y=0; y<8; y++)
                        if (desk[x][y]==n-1)
                        {
                                if (x<6 && y<7 && desk[x+2][y+1]==100)
                                        desk[x+2][y+1]=n;
                                if (x<6 && y>0 && desk[x+2][y-1]==100)
                                        desk[x+2][y-1]=n;
                                if (x>1 && y<7 && desk[x-2][y+1]==100)
                                        desk[x-2][y+1]=n;
                                if (x>1 && y>0 && desk[x-2][y-1]==100)
                                        desk[x-2][y-1]=n;
                                if (x<7 && y>1 && desk[x+1][y-2]==100)
                                        desk[x+1][y-2]=n;
                                if (x<7 && y<6 && desk[x+1][y+2]==100)
                                        desk[x+1][y+2]=n;
                                if (x>0 && y>1 && desk[x-1][y-2]==100)
                                        desk[x-1][y-2]=n;
                                if (x>0 &&y<6 && desk[x-1][y+2]==100)
                                        desk[x-1][y+2]=n;
                        }
                
        for(y=0; y<8; ++y)
        {
                 for(x=0;x<8; ++x)
                         cout<<desk[x][y]<<" ";
                 cout<<endl;
        }
        system("PAUSE");
}
Yandex
Объявления
18.03.2010, 12:34     Соединить шахматные 2 клетки кратчайшим путем коня
Ответ Создать тему
Опции темы

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