Ходы коня на шахматном поле 5x5

@Greenmars · Регистрация: 01.02.2016

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

Всем добрый вечер. Заинтересовала меня задача про коня на шахматном поле. Ее суть в том, чтобы определить, существует ли такой путь коня, когда он заезжает в клетку ровно один раз и обязательно должен пройти все клетки.
поискав в интернете материалы, нашел Алгоритм Варнсдорфа. По нему и написал код.
Но дело в том, что он не проходит все тесты из условия, а именно 4 из 5.
Вот код:

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
#include <iostream>
#include <cstdlib>
#include <stdio.h>
using namespace std;
int a[6][6];
int b[6][6];
void m1(int i, int j)
{
    int cnt = 0;
    if (i-2 > 0 && j+1 < 6 && a[i-2][j+1] != 1) ++ cnt;
    if (i-1 > 0 && j+2 < 6 && a[i-1][j+2] != 1) ++ cnt;
    if (i+1 < 6 && j+2 < 6 && a[i+1][j+2] != 1) ++ cnt;
    if (i+2 < 6 && j+1 < 6 && a[i+2][j+1] != 1) ++ cnt;
    if (i+2 < 6 && j-1 > 0 && a[i+2][j-1] != 1) ++ cnt;
    if (i+1 < 6 && j-2 > 0 && a[i+1][j-2] != 1) ++ cnt;
    if (i-1 > 0 && j-2 > 0 && a[i-1][j-2] != 1) ++ cnt;
    if (i-2 > 0 && j-1 > 0 && a[i-2][j-1] != 1) ++ cnt;
    b[i][j] = cnt;
}
void  ma(int i, int j)
{
    if (i-2 > 0 && j+1 < 6 && a[i-2][j+1] != 1) m1(i-2,j+1);
    if (i-1 > 0 && j+2 < 6 && a[i-1][j+2] != 1) m1(i-1,j+2);
    if (i+1 < 6 && j+2 < 6 && a[i+1][j+2] != 1) m1(i+1,j+2);
    if (i+2 < 6 && j+1 < 6 && a[i+2][j+1] != 1) m1(i+2,j+1);
    if (i+2 < 6 && j-1 > 0 && a[i+2][j-1] != 1) m1(i+2,j-1);
    if (i+1 < 6 && j-2 > 0 && a[i+1][j-2] != 1) m1(i+1,j-2);
    if (i-1 > 0 && j-2 > 0 && a[i-1][j-2] != 1) m1(i-1,j-2);
    if (i-2 > 0 && j-1 > 0 && a[i-2][j-1] != 1) m1(i-2,j-1);
}
 
 
int main()
{
     freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    char s[100], z[10];
    int n,m,cur,ii = 2, cnt = 1;
    cin >> s;
    if (s[0] == 'A') m = 1;
    else if (s[0] == 'B') m = 2;
    else if (s[0] == 'C') m = 3;
    else if (s[0] == 'D') m = 4;
    else if (s[0] == 'E') m = 5;
    z[0] = s[1];
    n = atoi(z);
    a[n][m] = 1;
        for (int i =1; i < 6; i ++)
            for (int j = 1; j < 6; j ++) b[i][j] = 30;
    while (true)
    {
        ma(n,m);
        cur = 30;
        for (int i = 1; i < 6; i ++)
            for (int j = 1; j < 6; j ++)
            {
                if (b[i][j] < cur)
            {
                cur = b[i][j];
                n = i;
                m = j;
            }
            }
 
    a[n][m] = 1;
    if (m == 1) s[ii] = 'A';
    else if (m == 2) s[ii] =  'B';
    else if (m == 3) s[ii] = 'C';
    else if (m == 4) s[ii] = 'D';
    else if (m == 5) s[ii] = 'E';
    if (n == 1) s[ii+1] = '1';
    else if (n == 2) s[ii+1] = '2';
    else if (n == 3) s[ii+1] = '3';
    else if (n == 4) s[ii+1] = '4';
    else if (n == 5) s[ii+1] = '5';
    ii += 2;
    for (int i =1; i < 6; i ++)
            for (int j = 1; j < 6; j ++) b[i][j] = 30;
    cnt ++;
    if (cnt == 25) break;
            if (cur == 0)
            {
                cout << 0;
                exit(0);
            }
    }
    for(int i =0; i <= ii -1; i ++)
        cout << s[i];
    return 0;
}

Кстати, если не ошибаюсь, почему-то выводит 0 на тесте A3. Помогите разобраться, в чем ошибка кода.
Данный алгоритм, вроде, должен работать.

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .