p1605 迷宫 题解
题目链接：https://www.luogu.com.cn/problem/P1605
首先，这是一道非常经典的题。这道题首先dfs，即深度优先搜索解题。因为题目问的是有多少种方法可以到达终点，所以采用dfs，若是问最佳的路径，则用bfs。
言归正传，这道题怎么做呢？
一、地图的储存
有一些同学开了两个数组，分别存放地图和走过标记，其实这样太麻烦了。因为走过和不能走（有障碍），都是同一种状态：走不了，所以，我们不妨只开一个数组，用这个数组存放走过和没有走过的标记。其中false表示没有走过，我们在程序的开始可以用memset把这个数组刷0，然后循环输入障碍的坐标，把这些坐标在数组中标位true，表示不能走。
二、搜索
首先我们要搞清楚搜索的状态。到达终点是最终的想要的状态，所以如果当前的坐标和终点坐标相同，那么就将sum（总和）的值+1，然后return继续搜索（因为递归使用栈来储存的，所以return之后，会回到上一层，也就是上一次的坐标状态）。
其次，我们要知道怎么在地图上进行运动。这个时候就需要用到屠龙刀——方向数组了。定义两个数组dx和dy，表示x和y的移动规律，因为题目要求朝上、下、左、右四个方向移动，所以数组大小为4。
在没有到达最终状态的时候，我们可以用一个for循环来控制坐标在图上移动。在落下移动之前要判断能否到达这个点：
1、这个点是false，即没有走过或不是障碍 2、这个点在n*m的范围内
最后进行深度优先搜索，将落下的这个点标位true（已经走过），然后继续搜索，在搜索到达return之后，把刚在落下的这个点，重新标为未走过。
代码：
#include<bits/stdc++.h>
using namespace std;
int m,n,t,sx,sy,fx,fy,sum;
int dx[4]={0,0,1,-1},
dy[4]={-1,1,0,0};
bool visited[100][6];
bool can(int x,int y)
{
bool b=true;
b=(x<=n)&&(y<=m);
b=b & ((x>=1) && (y>=1));
return b;
}
void dfs(int x,int y)
{
if(x==fx && y==fy)
{///到达终点
sum++;
return;
}
else
{
for(int i=0;i<=3;i++)
{///搜索方向
if(visited[x+dx[i]][y+dy[i]]==0 && can(x,y))
{///没有走过或可以走（即不为障碍）
visited[x][y]=1; ///标记为走过
dfs(x+dx[i],y+dy[i]); ///进一步由下一步搜索
visited[x][y]=0; ///回溯
}
}
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
memset(visited,0,sizeof(visited));///全部标位未走过 false
for(int i=1;i<=t;i++)
{///在map中只有两个状态，要么走过，要么未走过，
///因为走过之后就不能走了，所以他的状态和不能走是一样的，所以都用同一种方法表示
int x,y;
cin>>x>>y;
visited[x][y]=1; ///不能走的位置就是已经走过的位置 标位已走过 true
}
dfs(sx,sy);
cout<<sum<<endl;
return 0;
}