迷宫式回溯

Question

所以，我正在尝试用给定的开始和结束位置的 (X, Y) 坐标制作一个迷宫解算器，但我有一个条件：每次它从一个点到另一个点时，它应该检查是否有新的位置低于前一个 (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 函数以确保移动是否有效。

int visited[N][N]; 确保您不会一遍又一遍地访问同一个单元格。

迷宫式回溯

Maze-like backtracking

c

backtracking