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

@KeR · Регистрация: 05.12.2009

Студворк — интернет-сервис помощи студентам

ребят подскажите алгоритм и через чего лучше реализовывать, желательно предлагать самые простые варианты, подскажите пожалуста потом сделаю нароботки и чую продолжу спрашивать че да как(c++)

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

пример, но впроинципе можно чтоб и числами выдава, а не буквами чтоб типами хоть голову не мучать

@Грымзик · 17.03.2010, 16:58

Это поиск в ширину. Доска маленькая, поэтому можно совсем просто, без реализации очереди. Доска - это двумерный массив целых чисел. В начальную клетку ставишь значение 0, а в остальные например 100. На первом шаге смотришь в какие клетки можно попасть из начальных, и ставишь туда цифру 1. На втором просматриваешь всю доску, если встречается цифра 1, то смотришь куда можно пойти из нее, и если эта клетка имеет значение 100, то туда ставишь цифру 2. И так далее, пока на каком-либо шаге ты не сможешь сходить на конечную клетку. А потом надо будет вывести путь. В обратном порядке он ищется очень легко, просто из конечной клетки (пусть она имеет значение например 8) ищешь любую клетку, в которую можно из нее пойти, и которая имеет значение 7. Эта клетка будет последним шагом пути. Далее также рекурсивно ищешь предпоследний шаг пути (клетку со значением 6, в которую можно сходить из текущей клетки со значением 7).

@KeR · 18.03.2010, 08:32 **[ТС]**

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 и вот как мне дальше написать чтоб он искал следующую свободную клетку?

@Грымзик · 18.03.2010, 12:34

У Вас много ошибок и недочетов. Нельзя было выбирать число 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");
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

@KeR 0 / 0 / 0 Регистрация: 05.12.2009 Сообщений: 103

	Соединить шахматные 2 клетки кратчайшим путем коня 17.03.2010, 14:57. Показов 6918. Ответов 3 Метки нет (Все метки) ребят подскажите алгоритм и через чего лучше реализовывать, желательно предлагать самые простые варианты, подскажите пожалуста потом сделаю нароботки и чую продолжу спрашивать че да как(c++) пример, но впроинципе можно чтоб и числами выдава, а не буквами чтоб типами хоть голову не мучать 0

@Грымзик 2507 / 1483 / 37 Регистрация: 14.09.2009 Сообщений: 2,740
	17.03.2010, 16:58
	Сообщение было отмечено как решение Решение Это поиск в ширину. Доска маленькая, поэтому можно совсем просто, без реализации очереди. Доска - это двумерный массив целых чисел. В начальную клетку ставишь значение 0, а в остальные например 100. На первом шаге смотришь в какие клетки можно попасть из начальных, и ставишь туда цифру 1. На втором просматриваешь всю доску, если встречается цифра 1, то смотришь куда можно пойти из нее, и если эта клетка имеет значение 100, то туда ставишь цифру 2. И так далее, пока на каком-либо шаге ты не сможешь сходить на конечную клетку. А потом надо будет вывести путь. В обратном порядке он ищется очень легко, просто из конечной клетки (пусть она имеет значение например 8) ищешь любую клетку, в которую можно из нее пойти, и которая имеет значение 7. Эта клетка будет последним шагом пути. Далее также рекурсивно ищешь предпоследний шаг пути (клетку со значением 6, в которую можно сходить из текущей клетки со значением 7). 3

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

Решение