我想在运行程序时自动解决迷宫。
我的迷宫一开始是这样的。
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**
你们能帮我找到错误吗？
多亏了@HHLV，我已经想出了如何解决这个问题。
所以我的方法求解迷宫看起来像这样：
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;
}
并且知道它有效，谢谢！