c - 迷宫般的回溯

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]; 确保您不会一遍又一遍地访问同一个单元格。