一只老鼠走進了一個迷宮，如何從其中走出去，在此處我們用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");
}
~~~
運行結果為：
