c++ 练习

DFS 深度优先搜索

1. 结束判断条件
2. 循环枚举可能的情况
3. 判断当前情况是否合法
4. 恢复至之前模样

走出迷宫方法问题
从起点到终点，有多少种不同的方法

#include
using namespace std;
int cnt,n = 2;
int xi[4] = {-1,0,1,0};
int yi[4] = {0,1,0,-1};
int a[100],b[100];
bool st[10][10] ;
void DFS(int x,int y,int u)
{
if(x==n&& y==n){
cnt++;
for(int i=0;i<u;i++)
cout <<"("<< a[i] <<","<< b[i] <<")";
cout <<endl;
return;
}
for(int i=0;i<=3;i++)
{
int ix= x+xi[i], iy = y+yi[i];
if(st[ix][iy] || ixn ||iyn) continue;
st[ix][iy] = true;
a[u] = ix ,b[u] = iy;
DFS(ix,iy,u+1);
st[ix][iy] = false;
}
}
int main()
{
st[1][1] = true;
DFS(1,1,1);
cout << cnt;
return 0;
}