Передвижение коня по доске и сбор букв

@Andeangl · Регистрация: 18.07.2013

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

Добрый день!

Не могу разобраться, в чём проблема =(

Нужно решить задачу: есть шахматная доска. На ней, в каждой клетке, расположены буквы. По доске "ходит" конь (буквой "г", соответственно), и "собирает" фигуры. Нужно собрать таким образом 6 букв (первая "Э" уже задана).

К сожалению, кроме всякой ерунды, ничего не выдаёт =( Буду рад помощи.

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
#include <iostream>
#include <conio.h>
 
int hod(int, int, int, char[6]);
 
char desk[8][8] = { { 'и', 'р', 'м', 'о', 'и', 'в', 'о', 'о' },
                    { 'а', 'э', 'ч', 'а', 'д', 'в', 'о', 'ч' },
                    { 'о', 'м', 'о', 'и', 'д', 'м', 'а', 'л' },
                    { 'ы', 'с', 'т', 'и', 'и', 'т', 'о', 'е' },
                    { 'о', 'д', 'м', 'ы', 'о', 'э', 'п', 'м' },
                    { 'и', 'т', 'е', 'ф', 'с', 'м', 'б', 'п' },
                    { 'н', 'т', 'у', 'г', 'м', 'и', 'и', 'т' },
                    { 'с', 'л', 'ы', 'м', 'г', 'а', 'и', 'р' }
                    };
 
int main(){
    setlocale(0, "");
 
    hod(1, 1, 5, "э");
    _getch();
}
 
int hod(int _coord_x, int _coord_y, int _count_hod, char _str[6]){
    if (_count_hod == 0){
        std::cout << _str << " Конец" << std::endl;
        return 0;
    }
 
    if (_coord_x - 2 >= 0 && _coord_y + 1 <= 7){    // +
        hod(_coord_x - 2, _coord_y + 1, _count_hod - 1, _str + desk[_coord_x - 2][_coord_y + 1]);
    }
    if (_coord_x - 1 >= 0 && _coord_y + 2 <= 7){    // +
        hod(_coord_x - 1, _coord_y + 2, _count_hod - 1, _str + desk[_coord_x - 1][_coord_y + 2]);
    }
    if (_coord_x + 1 <= 7 && _coord_y + 2 <= 7){    // +
        hod(_coord_x + 1, _coord_y + 2, _count_hod - 1, _str + desk[_coord_x + 1][_coord_y + 2]);
    }
    if (_coord_x + 2 <= 7 && _coord_y + 1 <= 7){    // +
        hod(_coord_x + 2, _coord_y + 1, _count_hod - 1, _str + desk[_coord_x + 2][_coord_y + 1]);
    }
    if (_coord_x + 2 <= 7 && _coord_y - 1 >= 0){    // +
        hod(_coord_x + 2, _coord_y - 1, _count_hod - 1, _str + desk[_coord_x + 2][_coord_y - 1]);
    }
    if (_coord_x + 1 <= 7 && _coord_y - 2 >= 0){    // +
        hod(_coord_x + 1, _coord_y - 2, _count_hod - 1, _str + desk[_coord_x + 1][_coord_y - 2]);
    }
    if (_coord_x - 1 >= 0 && _coord_y - 2 >= 0){    // +
        hod(_coord_x - 1, _coord_y - 2, _count_hod - 1, _str + desk[_coord_x - 1][_coord_y - 2]);
    }
    if (_coord_x - 2 >= 0 && _coord_y - 1 >= 0){    // +
        hod(_coord_x - 2, _coord_y - 1, _count_hod - 1, _str + desk[_coord_x - 2][_coord_y - 1]);
    }
}

@DUMP · 11.07.2016, 01:25

Сообщение от Andeangl

кроме всякой ерунды

не удивительно, конь ходит один , а рекурсией получается , что у нас коней очень много.
+ то что вы делаете с char[6] не допустимо.

На 4 и 23 строчке меняем char на std::string и инклудим <string>.

C++
1
2
3
//Example
#include <string>
std::string _str

@Visus1 · 17.07.2016, 17:07

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
#include "stdafx.h"
#include "iostream"
#include "string"
using namespace std;
 
 
char desk[8][8] = { { 'и', 'р', 'м', 'о', 'и', 'в', 'о', 'о' },
                    { 'а', 'э', 'ч', 'а', 'д', 'в', 'о', 'ч' },
                    { 'о', 'м', 'о', 'и', 'д', 'м', 'а', 'л' },
                    { 'ы', 'с', 'т', 'и', 'и', 'т', 'о', 'е' },
                    { 'о', 'д', 'м', 'ы', 'о', 'э', 'п', 'м' },
                    { 'и', 'т', 'е', 'ф', 'с', 'м', 'б', 'п' },
                    { 'н', 'т', 'у', 'г', 'м', 'y', 'и', 'т' },
                    { 'с', 'л', 'ы', 'м', 'г', 'а', 'и', 'р' },
                    
};
int countd = 0;
string r;
int i = 0;
int dx[8] = {1,-2,-2,-1,-1,2,2,1};
int dy[8] = {2,-1,1,2,-2,1,-1,-2};
 
void DFS(int x,int y){
    
    if (x>= 0 && y <= 7){
    
        if (desk[y][x] != '1'){
        r += desk[y][x];
        countd += 1;
        desk[y][x] = '1';
        }else {return;}
    }else {
        return;
    }
    if(countd == 6){
    
           cout << r;
    }
    for (int i = 0; i < 8 && countd != 6;i++){
        DFS(x+dx[i],y+dy[i]);
    }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale (LC_CTYPE, "Rus");
    DFS(1,1);
    system("pause");
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .