（点赞，收藏，喜欢是对作者最大的鼓励和支持啊doge）

本次训练包含一道题目：

这是一道经典的计算机题目

包含考察了循环、递归、搜索、数组等多个知识点，可以方便同学们理解。

题面：

给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

输入方式：

第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出方式：

给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

题解：

首先我们先录入所以数据。

n表示行数，m表示列数，t表示障碍个数。

点（x1,y1)表示开始点，点（x2,y2)表示终点。

Map这个二维数组储存地图上每个点的状态，若一个点(a,b)可以走则Map[a][b]的值为0，若点(a,b)不可以走（存在障碍物，或者已经走过了），Map[a][b]的值就为1。

样例中用循环将t个障碍点的Map值标记为1。

#include
     
      int n,m,t;int Map[6][6];int x1,x2,y1,y2;int ans;	int main(){
            scanf("%d%d%d",&n,&m,&t);	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);	for(int i=1;i<=t;i++){
    		int a,b;		//printf("*");		scanf("%d%d",&a,&b);		Map[a][b]=1;	}}
     

之后我们开始从(x1,y1)点开始递归搜索。

主函数外：

void dfs(int a,int b){
    	if(Map[a][b]==1)return;	if(a==x2&&b==y2){
    		ans++;		return;	}	Map[a][b]=1;	if(a>1)dfs(a-1,b);	if(a
     
      1)dfs(a,b-1);	if(b
     

主函数内：

dfs(x1,y1);

首先我们定义一个void型函数，这个函数的参数有两个，a表示目前所在点的列数，b表示目前所在点的行数。这个函数表示我们处于（a,b）这个点上。

递归的第一步，我们先判定这个点是否为可以走的点，如果Map[a][b]==1说明这个点不可以走，所以就return结束这个函数，返回到上一层函数（上一个点）。

递归的第二步，判定这个点是否为终点，如果为终点就把答案加一，同事返回上一层函数（上一个点）。

递归第三部，先将目前这个点的Map值标记为1，表示这个点已经走过，然后判定边界的同时尝试向这个点的四个方向进行搜索移动。

最后在四个方向都搜索完成后，退出这个点，将这个点的Map值赋值为0，表示这个点可以被走，然后返回到上一层函数（上一个点）。

程序的最后输出ans的值就可以了。

附上源代码：

#include
     
      int n,m,t;int Map[6][6];int x1,x2,y1,y2;int ans;void dfs(int a,int b){
    	if(Map[a][b]==1)return;	if(a==x2&&b==y2){
    		ans++;		return;	}	Map[a][b]=1;	if(a>1)dfs(a-1,b);	if(a
      
       1)dfs(a,b-1);	if(b
      
     

后记，这个程序不是效率最高的程序，只是方便同学们理解，如果有其他更好的想法，欢迎一起讨论啊。。