迷宫般的回溯

Question

所以，我正在尝试使用开始和结束位置的给定（X，Y）坐标制作迷宫求解器，但我有一个条件：每次从一个点到另一个点时，它应检查新位置是否低于previous（a [x] [y] <= some_height_variabile）。到目前为止，这是我的代码：

#include <stdio.h>

#define N 4

int a[N][N] = 
{
    {35, 75, 80, 12}, 
    {13, 12, 11, 3}, 
    {32, 9, 10, 8}, 
    {12, 2, 85, 1}
};

int sol[N][N];

int h, k, count;
int end_x = -1, end_y = -1;
int start_x = -1, start_y = -1;

void print()
{
    int i, j;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (sol[i][j] > 0)
                printf("%d ", sol[i][j]);

            else
                printf("_ ");
        }
        printf("\n");
    }

    printf("\n");
}

int solution(int x, int y)
{
    return (x == end_x && y == end_y);
}

int valid(int x, int y)
{
    return (x >= 0 && x < N && y >= 0 && y < N && a[x][y] <= h && !sol[x][y]);
}

void back(int x, int y)
{
    if (valid(x, y))
    {
        k ++;
        sol[x][y] = k;
        h = a[x][y]; // right here I'm updating the variabile

        if (solution(x, y))
        {
            count ++;
            print();
        }
        else
        {
            back(x + 1, y);
            back(x, y + 1);
            back(x - 1, y);
            back(x, y - 1);
        }

        sol[x][y] = 0;
        h = a[x][y]; // I actually don't know where to put this
        k --;
    }
}

int main(void)
{
    int i, j;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            printf("%d ", a[i][j]);

        printf("\n");
    }

    while (start_x >= N || start_x < 0 || start_y >= N || start_y < 0)
    {
        printf(">> Start X: "); scanf("%d", &start_x);
        printf(">> Start Y: "); scanf("%d", &start_y);
    }

    h = a[start_x][start_y];

    while (end_x >= N || end_x < 0 || end_y >= N || end_y < 0)
    {
        printf(">> End X: "); scanf("%d", &end_x);
        printf(">> End Y: "); scanf("%d", &end_y);
    }

    printf("Generated solutions:\n");
    back(start_x, start_y);

    if (!count)
        printf("No path was found!\n");

    return 0;
}

因此，对于start_x = 0，start_y = 0，end_x = 1，end_y = 3它应该带来35 - > 13 - > 12 - > 11 - > 3和35 - > 13 - > 12-> 11 - > 10 - > 8 - > 3个解决方案。

没有这个条件，算法工作正常，只是我不知道在哪里更新h变量。

Answer 1

我认为你走在正确的轨道上。然而变量h似乎是多余的。相反，你还需要两件事：

1）您之前是否曾访问过某个特定的细胞。

2）您之前移动的值，因此当您移动到下一个单元格或考虑移动到下一个单元格时，您将验证它是否为有效移动。

您修改后的代码如下：

#include <stdio.h>

#define N 4

int a[N][N] =
{
    {35, 75, 80, 12},
    {13, 12, 11, 3},
    {32, 9, 10, 8},
    {12, 2, 85, 1}
};

int sol[N][N];
int visited[N][N];

int h, k, count;
int end_x = -1, end_y = -1;
int start_x = -1, start_y = -1;

void print()
{
    int i, j;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            if (sol[i][j] > 0)
                printf("%d ", sol[i][j]);

            else
                printf("_ ");
        }
        printf("\n");
    }

    printf("\n");
}

int solution(int x, int y)
{
    return (x == end_x && y == end_y);
}

int valid(int x, int y, int currentCellValue)
{
    return (x >= 0 && x < N && y >= 0 && y < N && a[x][y] <= currentCellValue && !sol[x][y] && !visited[x][y]);
}

void back(int x, int y, int curr)
{
    if (valid(x, y, curr))
    {
        k ++;
        sol[x][y] = k;
        visited[x][y] = 1;

        if (solution(x, y))
        {
            count ++;
            print();
        }
        else
        {
            back(x + 1, y, a[x][y]);
            back(x, y + 1, a[x][y]);
            back(x - 1, y, a[x][y]);
            back(x, y - 1, a[x][y]);
        }

        sol[x][y] = 0;
        visited[x][y] = 0;
        k --;
    }
}

int main(void)
{
    int i, j;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            printf("%d ", a[i][j]);

        printf("\n");
    }

    while (start_x >= N || start_x < 0 || start_y >= N || start_y < 0)
    {
        printf(">> Start X: "); scanf("%d", &start_x);
        printf(">> Start Y: "); scanf("%d", &start_y);
    }

    h = a[start_x][start_y];

    while (end_x >= N || end_x < 0 || end_y >= N || end_y < 0)
    {
        printf(">> End X: "); scanf("%d", &end_x);
        printf(">> End Y: "); scanf("%d", &end_y);
    }

    printf("Generated solutions:\n");
    back(start_x, start_y, a[start_x][start_y]);

    if (!count)
        printf("No path was found!\n");

    return 0;
}

在调用back期间，请注意我如何传递当前单元格的值，该值传递给isValid函数以确保移动是否有效。

qazxsw poi确保您不会一遍又一遍地访问同一个单元格。