0

Обойти матрицу 5#5 числами от 1 до 25.Возможные ходы (x+-3,y),(x,y+-3),(x+-2,y+-2).При 25 печатается решение ,но рекурсия продолжается. И правильное ли само решения/есть другие ошибки?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int move_back_a[26] = {}, move_back_b[26] = {}, ways[25] = {}, F[5][5] = {};
void array(int a, int b, int N)
{
    int i, j;
    F[a][b] = N;
    if (N == 0)
    {
        printf("no solutions");
        return;
    }
    if (N == 25)
    {
        for (i = 0; i < 5; i++)
        {
            for (j = 0; j < 5; j++) printf("%d ", F[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }
    if ((ways[N]<1) && (a + 3 < 5) && (F[a + 3][b] == 0))//  1 WAY
    {
        move_back_a[N + 1] = -3;
        move_back_b[N + 1] = 0;
        ways[N] = 1;
        array(a + 3, b, N + 1);
    }
    else if ((ways[N] < 2) && (b + 3 < 5) && (F[a][b + 3] == 0))//  2 WAY
    {
        move_back_b[N + 1] = -3;
        move_back_a[N + 1] = 0;
        ways[N] = 2;
        array(a, b + 3, N + 1);
    }
    else if ((ways[N] < 3) && (a - 3 >= 0) && (F[a - 3][b] == 0))//  3 WAY
    {
        move_back_a[N + 1] = 3;
        move_back_b[N + 1] = 0;
        ways[N] = 3;
        array(a - 3, b, N + 1);
    }
    else if ((ways[N] < 4) && (b - 3 >= 0) && (F[a][b - 3] == 0))//  4 WAY
    {
        move_back_b[N + 1] = 3;
        move_back_a[N + 1] = 0;
        ways[N] = 4;
        array(a, b - 3, N + 1);
    }
    else if (((ways[N] < 5) && a + 2 < 5) && (b + 2 < 5) && (F[a + 2][b + 2] == 0))//  5 WAY
    {
        move_back_a[N + 1] = -2;
        move_back_b[N + 1] = -2;
        ways[N] = 5;
        array(a + 2, b + 2, N + 1);
    }
    else if ((ways[N] < 6) && (a + 2 < 5) && (b - 2 >= 0) && (F[a + 2][b - 2] == 0))//  6 WAY
    {
        move_back_a[N + 1] = -2;
        move_back_b[N + 1] = 2;
        ways[N] = 6;
        array(a + 2, b - 2, N + 1);
    }
    else if ((ways[N] < 7) && (a - 2 >= 0) && (b + 2 < 5) && (F[a - 2][b + 2] == 0))//  7 WAY
    {
        move_back_a[N + 1] = 2;
        move_back_b[N + 1] = -2;
        ways[N] = 7;
        array(a - 2, b + 2, N + 1);
    }
    else if ((ways[N] < 8) && (a - 2 <= 0) && (b - 2 <= 0) && (F[a - 2][b - 2] == 0))//  8 WAY
    {
        move_back_a[N + 1] = 2;
        move_back_b[N + 1] = 2;
        ways[N] = 8;
        array(a - 2, b - 2, N + 1);
    }
    ways[N] = 0;
    F[a][b] = 0;
    array(a+move_back_a[N],b+move_back_b[N],N-1);
}
int main()
{
    int x, y;
    scanf("%d%d",&x,&y);
    x--;
    y--;
    array(x, y, 1);
    return(0);
}
2
  • Это int(&F)[5][5] никак не С. И еще - вы бы уточнили, что надо не заполнить матрицу, а обойти ее ходом некоторой фигуры, потому что заполнить - можно и построчно :)
    – Harry
    22 дек 2019 в 16:43
  • А по самому обходу что?
    – Skaze
    22 дек 2019 в 17:19

1 ответ 1

0

Ну, я бы делал так:

int board[5][5] = {0};

int dx[8] = { +3, -3,  0,  0, +2, +2, -2, -2 };
int dy[8] = {  0,  0, +3, -3, +2, -2, +2, -2 };

int move(int x, int y, int n)
{
    if (n > 25) return 1;
    for(int i = 0; i < 8; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > 4 || ny < 0 || ny > 4 || board[nx][ny]) continue;
        board[nx][ny] = n;
        if (move(nx,ny,n+1)) return 1;
        board[nx][ny] = 0;
    }
    return 0;
}

int main()
{
    int x, y;
    scanf("%d %d",&x,&y);
    board[--x][--y] = 1;
    move(x,y,2);
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
            printf("%3d",board[i][j]);
        puts("");
    }
}
6
  • Не совсем понимаю эту строчку if (move(nx,ny,n+1)) return 1; Идёт же проверка на возвращаемое? А возвращается 1 при N>25
    – Skaze
    22 дек 2019 в 17:46
  • 1 - путь сделан, можно выходить из всей рекурсии совсем; 0 - нет, надо продолжить работу...
    – Harry
    22 дек 2019 в 17:58
  • Всё остальное понятно. Спасибо.
    – Skaze
    22 дек 2019 в 18:05
  • А если количество обходов , то return 1 менять на return 0?
    – Skaze
    23 дек 2019 в 16:07
  • Гм... Тогда, по логике, тут if (n > 25) надо счетчик увеличивать, и возвращать 0... Вроде бы так.
    – Harry
    23 дек 2019 в 16:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.