本文共 3860 字，大约阅读时间需要 12 分钟。

练习1：递归倒置字符数组（题目链接可提交：）

完成一个递归程序，倒置字符数组。并打印实现过程

输入

字符数组长度及该数组 

输出

在求解过程中，打印字符数组的变化情况。 

样例输入

5 abcde

样例输出

ebcdaedcbaedcba

先注意两点：1.我们在写算法题的时候一般习惯在函数外部定义数组，为什么？因为主函数内的空间及其有限，2m大小，而主函数外部的存储空间极大以g为单位。全局变量在静态存储区分配内存，局部变量（定义在主函数内部的变量）是在栈上分配内存空间的。（c语言程序在运行时会动态创建一个堆栈段，里面存放着调用栈，保存着函数的调用关系和局部变量。）如果数组太大，可能会造成栈溢出。而且定义在全局区的变量我们不用赋初始值，默认为0，不论是变量还是数组。

2.swap函数，内部含有两个参数，如swap(a,b)，就是用来交换a和b的值。具体阐述：

题目思路：倒置字符串的过程是逐步进行的，开始的时候是交换头尾，每交换一次需要交换的字符的位置就向中间移动（从头开始交换的字符的位置向右移动，从尾开始交换的字符的位置向左移动），那么我们容易想到递归的思路就是模拟两个指针，每递归一次交换一次字符并在下一次递归的时候改变要交换的字符的位置。注意结束的条件：若是字符串的长度是偶数，那么结束的时候应该是两个指针的位置交叉，若是字符串的长度是奇数，结束的时候两个指针的位置应该指着同一个元素，所以结束条件应该是右边指针的位置小于等于左边指针的位置或者左边指针的位置大于等于右边指针的位置

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int len;char str[100010];                              //在全局区定义字符串数组，在函数内部就可以直接修改字符串，不需要传入指针，方便快捷 void dfs(int start,int finsh)                  {	if(finsh==1 || start>=finsh) return;       //若是字符串长度为1(也就是len=1)或者在逐渐交换头尾的过程中发现起始位置和结束位置重合了，就退出 	swap(str[start],str[finsh]);               //swap函数，用来交换这个字符串当前的start位置上的字符和finsh位置上的字符 	for(int i=1;i<=len;i++) cout<
       
        >len;	for(int i=1;i<=len;i++) cin>>str[i];       //输入从1开始长度为len的字符串 		dfs(1,len);                                //递归函数，输入起始位置和结束位置 	cout<
       
      
     
    
   

这个题目很经典，理解后多敲直至自己能够一遍敲对

~~~~~~~~~~~~~~~~~~~~~~~~我是分割线~~~~~~~~~~~~~~~~~~~~~~~~

练习2：走迷宫判断能否到达终点（洛谷链接可提交：）

高桥先生住的小区是长方形的，被划分成一个个格子。高桥先生想从家里去鱼店，高桥先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。

现在给出地图：

s：代表高桥先生的家

g：代表鱼店

.：代表道路

#：代表墙壁

高桥先生不能穿过墙壁。

输入：第一行输入n(1<=n<=500),m(1<=m<=500)代表小区的长和宽，接下来n行每行m个字符，描述小区中的每个格子。

输出：如果高桥先生能到达鱼店，输出"Yes"，否则输出"No"。

输入输出样例

输入 #1

4 5s####....#######...g

输出 #1

No

输入 #2

4 4...s.........g..

输出 #2

Yes

输入 #3

10 10s.........#########.#.......#.#..####.#.##....#.#.#####.#.#.g.#.#.#.#.#.#.#.#.#.###.#.#.#.#.....#...

输出 #3

No

输入 #4

10 10s.........#########.#.......#.#..####.#.##....#.#.#####.#.#.g.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#...

输出 #4

Yes

输入 #5

1 10s..####..g

输出 #5

No

很经典的走迷宫问题，打蓝桥的时候碰见迷宫问题肯定会感动到哭的，因为这题直接白给

注意1：由于我们需要走四个方向，因此我们需要一个数组来模拟我们四种选择（东西南北），然后用for循环来枚举我们现在选到的是哪个方向，若是判断我们向这个方向走是合法的（也就是不撞墙，不踩障碍等等）那就可以朝这个方向递归了。这道题我用了一种偷懒写法，没有定义数组表示方位，直接枚举了四个方向，但是一般的题目还是需要的~

注意2：用数组模拟方位的时候我们要注意程序中的xy轴和我们直角坐标系中的xy轴不太一样，程序中我们一般用x表示行，用y表示当前列，下面给张图演示一下

注意3：在递归过程中为了不走重复的格子（因为我们完全可以在第一个格子朝右走，然后在第二个格子又朝左走走回来，第一个题只能朝一个方向走，所以没有这方面的顾虑），我们还需要一个专门的判重数组用来标记走过的格子，当然走过一次的格子我们是不会再走啦，不然来回递归的话很可能会超时或者爆栈（dfs一般只适用于数据量较小的题目）

注意4：题目问我们是不是可以走到终点，那么若是我们走到了终点，就完全不需要再递归下去了，所以我们可以简化递归流程：设置一个flag标记变量，在我们搜到了目标点之后给flag赋值为1，那么若是flag的值为1，我们就再不需要递归下去了，直接return就好，这样可以节省时间提高效率

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int n,m,sx,sy,ex,ey;char map[1010][1010];int st[1010][1010];                   //全局区定义的st数组默认全部值都为0，我们把走过的点标记成1就可 int flag = 0;                         //若是我们走到了终点，flag就变成1，表示我们找到了终点 void dfs(int x,int y){	if(flag) return;		if(x<1||x>n||y<1||y>m||st[x][y]||map[x][y]=='#') return; //若是当前点超出了地图范围（1~n，1~m)或者走到了障碍物上面或者我们走过了，那么直接返回就可 		if(x==ex && y==ey)                //对当前点做终点判断 	{		flag = 1;                     //若是我们找到了终点，那么就把flag设为1，而且没有必要在递归下去了，直接return 		return;	}		st[x][y] = 1;                    //标记这个点表示我们走过了 	dfs(x+1,y);                      //朝下走一格	dfs(x,y+1);                      //朝右走一格	dfs(x-1,y);                      //朝上走一格	dfs(x,y-1);                      //朝左走一格	}int main(){	cin>>n>>m;	for(int i=1;i<=n;i++)		for(int j=1;j<=m;j++)			cin>>map[i][j];          //逐个字符读入迷宫 				for(int i=1;i<=n;i++)			for(int j=1;j<=m;j++)		{			if(map[i][j]=='s')       //找到起点个终点，起点坐标用sx，sy表示，终点坐标用ex，ey表示 			sx = i,sy = j;			if(map[i][j]=='g')			ex = i,ey = j;		}			dfs(sx,sy);                      //从起点开始搜（递归搜索） 	if(flag) cout<<"Yes";            	else cout<<"No";	return 0;	}
      
     
    
   

这也是一个极为经典的题目，大家一定要理解并且多敲几遍，不懂的直接问我

要加油哇！！！