今天的題目叫“迷宮問題(migong）”，是“DFS深度優先搜索 遞歸”一類的。
題目描述
設有一個N*N(2<=N<10)方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中
分別放0和1，0表示可通，1表示不能，入口和出口處肯定是0。迷宮走的規則如下所示：
即從某點開始，有八個方向可走，前進方格中數字為0時表示可通過，為1時表示不可通過，要另找路徑。找出所有從入口（左上角）到出口（右上角）的路徑(不能重復)，輸出路徑總數，如果無法到達，則輸出0。
輸入
第一行一個正整數n。
接下來2~n+1行 表示該迷宮。
輸出
輸出共一行，輸出路徑總數
輸入樣例
3 0 0 0 0 1 1 1 0 0
輸出樣例
2
提示
【數據范圍】2<=n<=10
解題：
#include <bits/stdc++.h>
using namespace std;
int sum,n;
bool a[15][15];
int dx[9]={0,0,0,1,-1,1,-1,1,-1};//八個方向
int dy[9]={0,1,-1,0,0,1,-1,-1,1};
void dfs(int x,int y)
{if(x==1&&y==n)//到達邊界{sum++;return;}for(int i=1;i<=8;i++)//八個方向{int tx=x+dx[i];//下一步要走的位置int ty=y+dy[i];if(tx>0&&ty>0&&tx<=n&&ty<=n&&a[tx][ty]==false){//能走a[tx][ty]=1;dfs(tx,ty);a[tx][ty]=0;//回溯}}
}
int main()
{cin >> n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin >> a[i][j];}}a[1][1]=1;dfs(1,1);cout << sum;return 0;
}
