老鼠走迷宫问题
最后更新于：2022-04-01 10:11:41
一只老鼠走进了一个迷宫，如何从其中走出去，在此处我们用2表示墙壁或障碍，0表示可以通过的路径通过深度搜索+回溯的方式可以解得答案老鼠每次选择一个方向前进，如果可以则继续深度搜索，否则换一个方向继续尝试。
如果各个方向都无法找到迷宫出口，则退回到老鼠到该点之前所在的点继续尝试其他方向实现代码如下：
~~~
//回溯法，也可以看作是一种深度搜索
#include <iostream>
using namespace std;
int g_nEndY = 5;
int g_nEndX = 6;
int g_nMapArr[7][7] = {
{2, 0, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 2, 0, 2, 2},
{2, 2, 0, 2, 0, 2, 2},
{2, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 0, 2}};
int MouseMove(int x, int y)
{
int nFlag = 0; //标志迷宫是否完成
g_nMapArr[x][y] = 1; //老鼠走过
if(x ==g_nEndX && y == g_nEndY) //已知迷宫出口和未知迷宫出口两种判断方式，如果未知，则判断边界条件
nFlag = 1;
if (nFlag == 0 && g_nMapArr[x][y+1] == 0 )
{
nFlag = MouseMove(x,y+1);
}
if (nFlag == 0 && g_nMapArr[x+1][y] == 0)
{
nFlag = MouseMove(x+1, y);
}
if (nFlag == 0 && g_nMapArr[x-1][y] == 0)
{
nFlag = MouseMove(x-1,y);
}
if(nFlag == 0 && g_nMapArr[x][y-1] == 0)
{
nFlag = MouseMove(x, y-1);
}
if (nFlag == 1)
{
return 1;
}
else
g_nMapArr[x][y] = 0; //撤销
return nFlag;
}
void main()
{
int nStartY = 0;
int nStartX = 1;
int nXLen = 7;
int nYLen = 7;
for (int i = 0; i< nYLen; i++)
{
for (int j = 0; j< nXLen; j++)
{
if (g_nMapArr[i][j] == 2)
{
cout<<"█";
}
else if (g_nMapArr[i][j] == 1)
{
cout<<"◇";
}
else
cout<<" ";
}
cout<<endl;
}
int nflag = MouseMove(nStartY, nStartX);
cout<<endl<<endl;
if (nflag == 0)
{
cout<<"Mouse can't get out"<<endl;
}
else
{
cout<<"迷宫路径"<<endl;
for (int i = 0; i< nYLen; i++)
{
for (int j = 0; j< nXLen; j++)
{
if (g_nMapArr[i][j] == 2)
{
cout<<"█";
}
else if (g_nMapArr[i][j] == 1)
{
cout<<"◇";
}
else
cout<<" ";
}
cout<<endl;
}
}
system("pause");
}
~~~
运行结果如下：
对于不止一条路径的情况该程序稍作修改就可以找出所有路径并统计其数目
~~~
//回溯法，也可以看作是一种深度搜索
//带有统计性质，其关键为每次达到预定条件后统计计数加一，然后撤销
#include <iostream>
using namespace std;
int nTotalWays = 0;
int g_nEndY = 7;
int g_nEndX = 8;
int nXLen = 9;
int nYLen = 9;
int g_nMapArr[9][9] = { {2, 2, 2, 2, 2, 2, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 0, 2, 2, 0, 2, 2, 0, 2},
{2, 0, 2, 0, 0, 2, 0, 0, 2},
{2, 0, 2, 0, 2, 0, 2, 0, 2},
{2, 0, 0, 0, 0, 0, 2, 0, 2},
{2, 2, 0, 2, 2, 0, 2, 2, 2},
{2, 0, 0, 0, 0, 0, 0, 0, 2},
{2, 2, 2, 2, 2, 2, 2, 0, 2}};
void PrintWay()
{
cout<<endl;
cout<<"第"<<nTotalWays<<"种迷宫路径"<<endl;
for (int i = 0; i< nYLen; i++)
{
for (int j = 0; j< nXLen; j++)
{
if (g_nMapArr[i][j] == 2)
{
cout<<"█";
}
else if (g_nMapArr[i][j] == 1)
{
cout<<"◇";
}
else
cout<<" ";
}
cout<<endl;
}
}
int MouseMove(int x, int y)
{
int nFlag = 0; //标志迷宫是否完成
g_nMapArr[x][y] = 1; //老鼠走过
if(x ==g_nEndX && y == g_nEndY) //已知迷宫出口和未知迷宫出口两种判断方式，如果未知，则判断边界条件
{
nFlag = 1;
}
if (nFlag == 0 && g_nMapArr[x][y+1] == 0 )
{
MouseMove(x,y+1);
}
if (nFlag == 0 && g_nMapArr[x+1][y] == 0)
{
MouseMove(x+1, y);
}
if (nFlag == 0 && g_nMapArr[x-1][y] == 0)
{
MouseMove(x-1,y);
}
if(nFlag == 0 && g_nMapArr[x][y-1] == 0)
{
MouseMove(x, y-1);
}
if (nFlag == 1)
{
nTotalWays++;
PrintWay();
}
g_nMapArr[x][y] = 0; //撤销
return nFlag;
}
void main()
{
int nStartY = 1;
int nStartX = 1;
for (int i = 0; i< nYLen; i++)
{
for (int j = 0; j< nXLen; j++)
{
if (g_nMapArr[i][j] == 2)
{
cout<<"█";
}
else if (g_nMapArr[i][j] == 1)
{
cout<<"◇";
}
else
cout<<" ";
}
cout<<endl;
}
MouseMove(nStartY, nStartX);
cout<<endl<<endl;
if (nTotalWays == 0)
{
cout<<"Mouse can't get out"<<endl;
}
else
cout<<"共有"<<nTotalWays<<"种走法"<<endl;
system("pause");
}
~~~
运行结果为：
