深度优先搜索大概的框架如下：

int dfs(int x,int y,int step)
{
	if(达到目标状态)
	{
		//进行对应操作：
        
		return 0;
	}

	//遍历所有情况
	for(int i=0;i<n;i++)
	{
		if(vist[i]==0)    //如果没有被访问或者没有越界非法
		{
			对x，y进行更新：
            走下一步：

			vist[i]=1;
			dfs(x,y,step);
			vist[i]=0;    //记得要还原
		}
	}
	return 0;
}

简单一题：DFS全排列

例如：

输入：3

输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


#include<iostream>
#include<algorithm>
#include<cstring>
int a[10];     //原排列数组
int vist[10];  //记录是否被访问过
int b[10];     //放新生成的一组排列
int n;
void dfs(int step)
{
        //达到目的状态就返回了
	if(step==n)
	{
		for(int i=0;i<n;i++)
			printf("%2d",b[i]);
	    printf("\n");
		return;
	}

	//否则  遍历所有情况
	for(int i=0;i<n;i++)
	{
		if(vist[i]==0)
		{
			b[step]=a[i];
			vist[i]=1;   //继续深搜
			dfs(step+1); //不要写成 step++ 或者  ++step
			vist[i]=0;  //记得还原
		}
	}
	return ;
}

int main()
{
	memset(vist,0,sizeof(vist));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	a[i]=i+1;
	dfs(0);
	return 0;
}

第二题：营救小明

输入n方阵，1表示障碍物，0表示通路，给出小明的坐标，求最短路径。

例如：

输入：
4
0 0 0 0
1 1 0 0
0 1 0 0
0 1 0 0
2 1

输出：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
int map[20][20];
int vist[20][20];//访问标记 
int x1,y1;
int n;int minStep=9999999;
int dis[4][2]={
	{-1,0},{1,0},{0,-1},{0,1}	//上下左右四个方向 
};

void dfs(int x,int y,int step)
{
	//判断是否到了小明的位置
	if(x==x1&&y==y1)
	{
		if(step<minStep)
		minStep=step;
		return ;
	}
	//没有走到小明的位置则枚举下一步可能的四种走法 
	
	int nextX,nextY;
	for(int i=0;i<=3;i++)
	{
		nextX=x+dis[i][0]; 
		nextY=y+dis[i][1];
		//判断有墙壁吗？前面走过吗？ 
		if(map[nextX][nextY]==1||vist[nextX][nextY]==1)
		continue;
		//判断越界 
		if(nextX>=n||nextX<0||nextY>=n||nextY<0)
		continue; 
		//排除了上面两种可能才能确定下一步坐标 
		
		vist[nextX][nextY]=1;
		++step;
		dfs(nextX,nextY,step);
		vist[nextX][nextY]=0;
		
	} 
	return ; 
	
} 
int main()
{
	cin>>n;
	//输入地图map 
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	{
		cin>>map[i][j];
	} 
	cin>>x1>>y1;
	vist[0][0]=1;
	dfs(0,0,0); 
	cout<<minStep<<endl;
	return 0;
}

第三题：湖的数量（最大连通子图个数）

该题与前面最大不同就是访问标记的巧妙设计，这里可以直接用数组本身当做访问标记，但是以上的题目必须借助vist[ ] 数组，而且后面要记得还原。这里就不用还原。

输入n，m 表示n行m列，由‘W'、’.‘ 组成，W表示水， ‘.’ 表示陆地问湖的数量是多少？

例如：

输入：

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出：3

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;

char arr[102][102];
int dis[][2]={
		{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}
	}; //方向数组 上》》顺时针》》左上

int dfs(int x,int y)
{
	//这一题没有目的状态，唯一的目的就是，找到一个W就深入把里面所有W改成点‘.’ 然后在继续探索
	arr[x][y]='.';
	int nextX,nextY;
	//尝试往8个方向试探
	for(int i=0;i<8;i++)
	{
		nextX=x+dis[i][0];
		nextY=y+dis[i][1];

		//判断下一个坐标不合法或者不是水
		if(nextX<0||nextX>=n||nextY<0||nextY>=m||arr[nextX][nextY]=='.')
			continue;
		else
			dfs(nextX,nextY);
		
	}
	return 0;
}

int main()
{
	


	cin>>n>>m;
	for(int k=0;k<n;k++)
	for(int j=0;j<m;j++)
	cin>>arr[k][j];

	int ans=0;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		if(arr[i][j]=='W')
		{
			ans++;
			dfs(i,j);
		}
	}

	cout<<ans<<endl;
	return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
int ans=0;
int arr[50];
int index[50];//记录下标用的
int vist[50];
//判断是否是素数
int perm(int n)
{
	for(int i=2;i<sqrt(n);i++)
		if(n%i==0)
			return 0;
	return 1;
}

int dfs(int step)
{
	//达到目标状态
	if(step==m)  //如果凑够了m个数，注意m从0开始所以是m结束
	{
		int sum=0;
		for(int i=0;i<m;i++)
		{
			sum+=arr[ index[i] ];
		}
		if(perm(sum))
			ans++;
		

		return 0;
		
	}
	//枚举每一种情况
	for(int i=0;i<n;i++)
	{
		if(vist[i]==0)
		{
			vist[i]=1;
			index[step]=i;
			dfs(step+1);
			index[i]=0;
		}
	}

	return 0;
}

int main()
{
	memset(vist,0,sizeof(vist));
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	dfs(0);
	cout<<ans<<endl;
	return 0;
}

第六题（模板题）：

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。（1<=m,n<=100）?

输入输出格式

输入格式：

输入：整数m,n(m行，n列)

矩阵

输出格式：

输出：细胞的个数

输入输出样例

输入样例#1：

输出样例#1：

该题与上面第三题一样，只是形式换了一下而已。我画了一张图理解题意。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
int ans=0;
char arr[102][102];
//int vist[50];

int dis[4][2]={
				{-1,0},{0,1},{1,0},{0,-1}  //上右下左的方向 
			};

int dfs(int x,int y)
{
	
	arr[x][y]='0';  //走过标记为0
	
	//遍历所有走法
	int nextX,nextY;
	for(int i=0;i<4;i++) 
	{
		nextX=x+dis[i][0];
		nextY=y+dis[i][1];
		
		//判断下一步是否有效 
		if(nextX<0||nextX>=n||nextY<0||nextY>=m||arr[nextX][nextY]=='0')
		continue;
		else
		dfs(nextX,nextY);
	}
	return 0;
}
 
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	cin>>arr[i][j];
	
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	{
		if(arr[i][j]!='0')
		{
			ans++;
			dfs(i,j);
		}
	}

	cout<<ans<<endl;
	return 0;
}

深搜（DFS）简单理解