c - 老鼠迷宫谜题的解数

Question

迷宫拼图中的老鼠 - 迷宫以 N*N block 的二进制矩阵形式给出，其中源 block 是最左上角的 block ，即迷宫 [0][0]，目标 block 是最右下角的 block ，即迷宫 [N -1][N-1]。老鼠从源头出发，必须到达目的地。老鼠可以向任何方向移动:向前、向下、向左、向右。在迷宫矩阵中，0表示该 block 是死胡同，1表示该 block 可以在从源到目的地的路径中使用。

问题 - 找到所有可能的解决方案以及将老鼠带出迷宫的解决方案的数量。我能够为老鼠在迷宫中找到“单一解决方案”。但如何确定不同的可能解以及解的数量呢？粘贴下面的代码将确定一个解决方案并打印相同的结果。请帮助我如何确定不同的可能解决方案以及解决方案的数量。

#include<stdio.h>
#include<conio.h>
#define N 5 //Maze Size 5X5 matrix

//Function declarations
void maze(int m[N][N]);
int maze_soln(int soln[N][N], int m[N][N],int ,int,int path[N][N]);
int issafe(int m[N][N], int x, int y,int path[N][N]);

// This function checks for valid cell. If already visited in the past
// path[][] will take care of returning false.
int issafe(int m[N][N], int x, int y,int path[N][N])
{
    if (x >= 0 && y >= 0 && x < N && y < N && m[x][y] == 1 && path[x][y] !=1)
        return true; // Valid cell.
    else
        return false;
}

// Maze solutions. Checks for proper cell. finds proper path 
// By going LEFT,RIGHT,UP or DOWN
int maze_soln(int soln[N][N], int m[N][N],int x,int y,int path[N][N])
{
    //All the cells have been visited
    if (x == N - 1 && y == N - 1)
    {
        soln[x][y] = 1; //mark the cell as possible path
        return true;
    }

    // Find out different paths
    if (issafe(m, x, y,path) == true)
    {
        soln[x][y] = 1; // mark the cell as possible solution
        path[x][y] = 1; //mark the path as visited

        // Go RIGHT and see if there's a path
        if (maze_soln(soln, m, x, y + 1,path))
            return true;

        //LEFT
        if (y> 0 && maze_soln(soln, m, x, y-1,path))
            return true;

        //DOWN
        if (maze_soln(soln, m, x + 1, y,path))
            return true;

        //UP
        if (x>0 && maze_soln(soln, m, x - 1, y,path))
            return true;

        soln[x][y] = 0;
        return false;
    }
    return false;
}

// Prints the solution matrix if proper path is found
void maze(int m[N][N])
{
    int i, j;
    int soln[N][N] = { 0 };
    int path[N][N] = { 0 };
    if (maze_soln(soln, m, 0, 0,path) == true)
    {
        printf("\n Solution\n"); //Print solution matrix
        for (i = 0; i < N; i++)
        {
            for (j = 0; j < N; j++)
            {
                printf("\t%d", soln[i][j]);
            }
            printf("\n");
        }
    }

    return;
}

// Main function
int main()
{
    int i, j;
    //Maze matrix
    int m[N][N] = { { 1,1,1,0,0 },
                    { 1,1,0,1,0 },
                    { 0,1,0,1,1 },
                    { 1,1,1,1,1 },
                    { 1,0,0,1,1 } };

    //Print the Maze
    printf("MAZE\n");
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
        {
            printf("\t%d", m[i][j]);
        }
        printf("\n");
    }

    //Call maze function to find out the path
    // and print the solution matrix
    maze(m);
    _getch();
}

Answer 1

当你找到第一个解决方案时，你会提前返回。如果你想看到更多的解决方案，你必须继续前进并探索所有路径。您的核心函数现在返回的是解决方案的数量，而不是真值。

当然，当您找到解决方案时，您必须将其存储起来，以便以后可以打印它们。这可能会占用大量内存，因为在稀疏迷宫中可能有许多可能的解决方案。您也不知道预先有多少种解决方案。

因此，一个简单的替代方案是在找到当前解决方案后打印它。

与您的问题无关，但您实际上并不需要三个单独的数组。当您添加另一个可能的值(访问空间)时，您可以使用原始的墙壁和空间数组。该值充当面包屑，告诉您已经去过哪里。有效的下一步只能是到达未访问过的空间。

将其付诸实践，您会得到，例如:

#include <stdio.h>

#define N 5

int issafe(int m[N][N], int x, int y)
{
    if (x < 0 || x >= N) return 0;
    if (y < 0 || y >= N) return 0;

    return (m[x][y] == 1);
}

void print(int m[N][N])
{
    static const char *glyph = "#.*";
    static int nsol = 0;
    int i, j;

    printf("Solution %d\n\n", ++nsol);

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            putchar(glyph[m[i][j]]);
        }
        putchar('\n');
    }
    putchar('\n');
}

int maze(int m[N][N], int x, int y)
{
    int nsol = 0;

    if (issafe(m, x, y)) {
        m[x][y] = 2;

        if (x == N - 1 && y == N - 1) {
            print(m);
            nsol = 1;
        } else {
            nsol += maze(m, x, y + 1);
            nsol += maze(m, x, y - 1);
            nsol += maze(m, x + 1, y);
            nsol += maze(m, x - 1, y);
        }

        m[x][y] = 1;
    }

    return nsol;
}

int main()
{
    int m[N][N] = { 
        { 1, 1, 1, 0, 0 },
        { 1, 1, 0, 1, 0 },
        { 0, 1, 0, 1, 1 },
        { 1, 1, 1, 1, 1 },
        { 1, 0, 0, 1, 1 } 
    };
    int nsol;

    nsol = maze(m, 0, 0);
    printf("%d solutions.\n", nsol);

    return 0;
}