解决迷宫c#

Question

我想在运行程序时自动解决迷宫问题.

我的迷宫在开始时就像这样.

1 0 0 0
0 0 1 0
0 1 1 0
0 1 1 0

最后它应该是这样的:

0 1 1 1
1 1 0 1
1 0 0 1
1 0 0 1

我有一个3维数组(行,列和侧).

侧面可以在(0),右(1),上(2)和左(3)之下.如果我有墙,我会检查每个单元格.如果是的话,我在那个单元格中放了一个.

mazeTab[0, 0, 0] = 0;
mazeTab[0, 0, 1] = 1;
mazeTab[0, 0, 2] = 1;
mazeTab[0, 0, 3] = 1;

mazeTab[1, 0, 0] = 0;
mazeTab[1, 0, 1] = 0;
mazeTab[1, 0, 2] = 1;
mazeTab[1, 0, 3] = 1;

mazeTab[2, 0, 0] = 0;
mazeTab[2, 0, 1] = 0;
mazeTab[2, 0, 2] = 1;
mazeTab[2, 0, 3] = 0;

mazeTab[3, 0, 0] = 0;
mazeTab[3, 0, 1] = 1;
mazeTab[3, 0, 2] = 1;
mazeTab[3, 0, 3] = 0;
//=================================

mazeTab[0, 1, 0] = 0;
mazeTab[0, 1, 1] = 0;
mazeTab[0, 1, 2] = 1;
mazeTab[0, 1, 3] = 1;

mazeTab[1, 1, 0] = 1;
mazeTab[1, 1, 1] = 1;
mazeTab[1, 1, 2] = 0;
mazeTab[1, 1, 3] = 0;

mazeTab[2, 1, 0] = 1;
mazeTab[2, 1, 1] = 1;
mazeTab[2, 1, 2] = 1;
mazeTab[2, 1, 3] = 1;

mazeTab[3, 1, 0] = 0;
mazeTab[3, 1, 1] = 1;
mazeTab[3, 1, 2] = 0;
mazeTab[3, 1, 3] = 1;
//===================================
mazeTab[0, 2, 0] = 0;
mazeTab[0, 2, 1] = 1;
mazeTab[0, 2, 2] = 0;
mazeTab[0, 2, 3] = 1;

mazeTab[1, 2, 0] = 1;
mazeTab[1, 2, 1] = 1;
mazeTab[1, 2, 2] = 1;
mazeTab[1, 2, 3] = 1;

mazeTab[2, 2, 0] = 1;
mazeTab[2, 2, 1] = 1;
mazeTab[2, 2, 2] = 1;
mazeTab[2, 2, 3] = 1;

mazeTab[3, 2, 0] = 0;
mazeTab[3, 2, 1] = 1;
mazeTab[3, 2, 2] = 0;
mazeTab[3, 2, 3] = 1;
//===================================
mazeTab[0, 3, 0] = 1;
mazeTab[0, 3, 1] = 1;
mazeTab[0, 3, 2] = 0;
mazeTab[0, 3, 3] = 1;

mazeTab[1, 3, 0] = 1;
mazeTab[1, 3, 1] = 1;
mazeTab[1, 3, 2] = 1;
mazeTab[1, 3, 3] = 1;

mazeTab[2, 3, 0] = 1;
mazeTab[2, 3, 1] = 1;
mazeTab[2, 3, 2] = 1;
mazeTab[2, 3, 3] = 1;

mazeTab[3, 3, 0] = 0;
mazeTab[3, 3, 1] = 1;
mazeTab[3, 3, 2] = 0;
mazeTab[3, 3, 3] = 1;

然后我用一种方法来解决整个迷宫,但我很确定有些问题.当我使用它时,我检查下一个单元格,例如:如果我有一个0并且我可以进入上面,我检查上面的单元格是否也可以进入下面的单元格,以验证我们没有一个墙那里.

   int solvemaze(int horizontal, int vertical,int cote)
    {

        //horizontalestination is the last cell(maze[taille-1][taille-1])
        if ((horizontal == taille - 1) && (vertical == taille - 1))
        {
            solution[horizontal,vertical] = 1;
            return 1;
        }

        if (horizontal >= 0 && vertical >= 0 && horizontal < taille && vertical < taille && solution[horizontal,vertical] == 0)
        {

            printsolution();
            //if safe to visit then visit the cell
            solution[horizontal,vertical] = 1;
            //under
            if (mazeTab[horizontal,vertical,cote]==0)
                return solvemaze(horizontal,vertical+1,(cote+1)%4);
            cote = (cote + 1) % 4;
            //right
            if (mazeTab[horizontal, vertical, 1] == 0)
                return solvemaze(horizontal+1, vertical, (cote + 1)% 4);
            cote = (cote + 1) % 4;
            //up
            if (mazeTab[horizontal, vertical, 2] == 0)
                return solvemaze(horizontal, vertical -1, (cote + 1) % 4);
            cote = (cote + 1) % 4;
            //left
            if (mazeTab[horizontal, vertical, 3] == 0)
                return solvemaze(horizontal -1, vertical, (cote + 1) % 4);
            cote = (cote + 1) % 4;
            //backtracking
            solution[horizontal,vertical] = 0;
            return 1;
        }
        return 1;

只是提醒你,如果你可以去一个特定的细胞,那么它就是1.所以解决迷宫的路径是1.

最后,我在0,3,0单元格开始迷宫,就是这个:

1 0 0 0
0 0 1 0
0 1 1 0
**0** 1 1 0

当我跑步时,这就是我所得到的:

0 1 1 1 
1 1 0 0 
1 0 0 0 
0 0 0 0

以下0应该已经输入1 ..

0 1 1 1 
1 1 0 **0** 
1 0 0 **0** 
**0** 0 0 **0**

你们能帮我找到错误吗？

Answer 1

感谢@HHLV，我已经找到了解决这个问题的方法。

所以我的方法solvemaze看起来像这样：

int solvemaze(int horizontal, int vertical, int cote)
    {


        if ((horizontal == taille - 1) && (vertical == taille - 1))
        {
            solution[vertical, horizontal] = 1;
            return 1;
        }

        if (horizontal >= 0 && vertical >= 0 && horizontal < taille && vertical < taille && solution[vertical, horizontal] == 0)
        {

            printsolution();
            //if safe to visit then visit the cell
            solution[vertical, horizontal] = 1;

            for (int i = 0; i < 3; i++)
            {

                if (mazeTab[horizontal, vertical, cote] == 0)
                {
                    if (cote == 0 && solvemaze(horizontal, vertical + 1, (cote + 3) % 4) == 1)
                    {
                        return 1;
                    }
                    else if (cote == 1 && solvemaze(horizontal + 1, vertical, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                    else if (cote == 2 && solvemaze(horizontal, vertical - 1, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                    else if (cote == 3 && solvemaze(horizontal - 1, vertical, (cote + 3) % 4) == 1)
                    {
                        return 1;

                    }
                }
                cote = (cote + 1) % 4;

            }

            //backtracking
            solution[vertical, horizontal] = 0;

            return 0;
        }
        return 0;

    }

并知道它有效，谢谢！