深度优先搜索算法（DFS）_深度优先搜索之孙悟空救唐僧

过程：

对每一个可能的分支路径深入到不能再深入为止。而且每个节点只能访问一次

【第一题：孙悟空找师傅】

问题描述:

西游路上咱们的唐长老又一次被妖怪抓走了。已知妖怪洞穴是一个N*N 的正方形，其中有一些假山堵路。
输入:第一行是一个正整数N(2<N<10),后面包含N*N行由0，1，2组成的矩阵，其中0表示可以走，1表示假山，2表示师傅的位置。
输出:如果悟空和八戒可以救出师傅就输出YES，否则就输出NO。
样例输入1:

4
0 0 0 0
0 1 0 1
1 0 0 1
1 1 0 2

样例输出1:
 

YES

样例输入 2：

3
0 0 0
0 1 1
0 1 2

样例输入2:

NO

运用递归的思想，在二维的数组里面遍历上下左右四个方向

代码实现：

#include<iostream>
using namespace std;
 
int dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};//控制搜索方向
								//确保四个方向能够搜到 
int G[105][105],vis[105][105];  //G存储地图，
								//vis标记是否搜索过 
int n;//n为地图的长和宽 
bool f=false;//标记是否能够找到师傅 
void dfs(int x,int y){//如果找到师傅则结束 
	if(G[x][y]==2){
		cout<<x<<" "<<y<<endl;
		f=true;
		return; 
	}
	//开始搜索 
	for(int i=0;i<4;i++){ //四个方向 
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&xx<n&&yy>=0&&yy<n&&G[xx][yy]!=1&&vis[xx][yy]==0){
			vis[xx][yy]=1;//标记xx yy位置已经搜索过了 
			dfs(xx,yy);//从xx yy位置开始搜索 
			vis[xx][yy]=0;//回溯 
		}
	}
} 
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>G[i][j];
		}
	}
	if(G[0][0]==1){
		cout<<"NO"<<endl;
		return 0;
	} 
	else if(G[0][0]==2){
		cout<<"YES"<<endl;
		return 0;
	}
	else{
		vis[0][0]=1;//标记0 0 位置搜索过了 
		dfs(0,0);
		if(f){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}
	
	
	
	return 0;
} 

【第二题：传送门】

问题描述:

观音有一件法宝，叫做传送门，我们可以通过这件法宝从妖怪洞穴出去了，观音把这件法宝放在了一个妖怪洞穴，我们只要找到那个洞穴就可以出去了。观音已经把放法宝洞穴的坐标告诉我们了，我们需要编程确定一下是否能到达那个洞穴就行了。

输入:第一行包含一个正整数N(1<n<30)表示迷宫的长和宽，下面N行，每行有N个数字，其中1表示可以走，0表示死路。接下来两行分别表示悟空和师傅所在洞穴坐标和传送门所在洞穴坐标。

输入:如果悟空他们可以成功走到传送门空间就输出YES，否则就输出 No。

样例输入:

5
1 0 0 1 0
1 1 1 1 1
1 0 1 0 0
1 0 1 1 1
0 1 0 1 0
4 4
2 1

样例输出:

YES

代码实现：

#include<iostream>
using namespace std;
int dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};//遍历方向 
int n;//存储地图
int G[1001][1001],vis[1001][1001];//G存储地图，vis标记是否被搜索过
bool f=false;//存储是否找到传送门 
int sx,sy,cx,cy;
void dfs(int x,int y){
	if(x==cx&&y==cy){
		cout<<"YES"<<endl;
		f=true;
		return ;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&G[xx][yy]!=0&&vis[xx][yy]==0){
			vis[xx][yy]=1;
			dfs(xx,yy);
			vis[xx][yy]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>G[i][j];
		}
	}
	cin>>sx>>sy;
	cin>>cx>>cy;
	if(sx==cx&&cy==sy){
		cout<<"YES"<<endl;
		return 0;
	}
	vis[sx][sy]=1;
	dfs(sx,sy);
	if(f==false){
		cout<<"NO"<<endl;
	}	
	return 0;
} 

---

 路径版：

样例输入：

5
1 0 0 1 0
1 1 1 1 1
1 0 1 0 0
1 0 1 1 1
0 1 0 1 0
4 4
2 1

 样例输出:

(4,4)->(4,3)->(3,3)->(2,3)->(2,2)->(2,1)

 代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=101;
int n; 
int x,y,cx,cy;
int G[N][N],vis[N][N];
int A[300][3]; 
bool f=false;
int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
void dfs(int x,int y,int d){
	if(x==cx&&y==cy){
		f=true;
		for(int i=0;i<d-1;i++){
			cout<<"("<<A[i][0]<<","<<A[i][1]<<")->";
		}
		cout<<"("<<cx<<","<<cy<<")"<<endl;
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=1&&yy>=1&&xx<=n&&yy<=n&&G[xx][yy]==1&&vis[xx][yy]==0){
			vis[xx][yy]=1;
			A[d][0]=xx;
			A[d][1]=yy;
			dfs(xx,yy,d+1);
			vis[xx][yy]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>G[i][j];
		}
	}
	cin>>x>>y>>cx>>cy;
	if(x==cx&&y==cy){
		cout<<"YES"<<endl;
		return 0;
	}
	else{
		vis[x][y]=1;
		A[0][0]=x;
		A[0][1]=y;
		dfs(x,y,1);
		if(!f)  cout<<"NO"<<endl;
	}
	
	
	
	return 0;
}

【题目三：西游记之海域分块】

问题描述:

最近天气炎热，人鱼王国水位下降陆地露出海面，把王国分成了几个部分，国王的命令无法传达给公民，让红烧鱼国王感觉非常苦恼，所以国王想要请悟空帮忙给各个水域传递一个消息。虽然人鱼王国不大，但是如果悟空每个地方都去一次就会耽误很长时间，影响取经大业，所以悟空决定先计算一下陆地把人鱼王国分成了几部分。输入:第一行包合两个正整数N和M(1<N,M<30)表示人鱼王国的长和宽，下面是一个N行M列的二维数组，其中1表示陆地，0表示海水。

输入:一个整数a，表示陆地把海域分成的份数(斜着方向不算连通)。

样例输入:

5 5
1 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 0 0 1 1
0 1 0 1 0

样例输出:

6

核心思路:
从第一行开始从左向右开始遍历，如果当前位置是0，就从当前位置开始向四周深搜，把相连的0都变成1

#include<iostream>
using namespace std;
int n,m;
int G[1001][1001];
int dx[5]={1,0,-1,0},dy[5]={0,1,0,-1};
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&xx<n&&yy>=0&&yy<n&&G[xx][yy]==0){
			G[xx][yy]=1;
			dfs(xx,yy);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>G[i][j];
		}
	}
	int res=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(G[i][j]==0){
				G[i][j]=1;
				dfs(i,j);
				res++;
			}
		}
	} 
	cout<<res<<endl; 
	return 0;
}

【题目四： 国王的神器 】

问题描述:

红烧鱼国王拿出了祖传神器(水管)，他可以使斜对角的海域连通，这样悟空就可以少通知一些地方了，真是个不错东西，我们-起来计算一下使用神器后，悟空需要通知几个海域。
输入:第一行包含两个正整数N和M(1<N,M<30)表示人鱼王国的长和宽，下面是
一个N行M列的二维数组，其中1表示陆地，0表示海水。
输入:一个整数a表示陆地把海域分成的份数(斜着方向连通)。

样例输入:

5 5
1 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 0 0 1 1 
0 1 0 1 0   

样例输出:

2

代码实现：

#include<iostream>
using namespace std;
 
int G[1001][1001];
int n,m,mins=2147483647,sum=0;
int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
void dfs(int x,int y){
	for(int dx=-1;dx<=1;dx++){
		for(int dy=-1;dy<=1;dy++){
			int xx=x+dx;
			int yy=y+dy;
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&G[xx][yy]==0){ 
				G[xx][yy]=1;
				dfs(xx,yy);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>G[i][j];
		}
	}
	int res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(G[i][j]==0){
				if(G[i][j]==0){
					G[i][j]=1;
					dfs(i,j);
					res++; 
				}
			}
		} 
	}
	cout<<res<<endl;
	return 0;
} 

【题目五：唐僧去哪儿】

问题描述:

历经磨难，悟空和三藏终于逃出魔爪，正准备去找沙僧等人，问题又来了。他们的位置离沙僧比较远，现在有一副地图。地图每个位置都有一个数字表示经过这个位置需要用的时间(本来就一个筋斗云的事，带着师傅就是麻烦)

地图如下:

 1  6  6  6 

15  7  6  6 

15  3  6  6 

15 15 1  1 

输入:第一行包含两个正整数N和M(1<N,M<30)表示人鱼王国的长和宽下面一行包含4个整数，前两个数表示猴哥和师傅的位置，后面两个数表示沙僧位置，最后是一个N行M列的二维数组，每个数字表示走当前位置需要用的时间。

输出:一个整数，表示最短时间。

样例输入: 

4 4 
1 1 4 4 
1 6 6 6 
15 7 6 6 
15 3 6 6 
15 15 1 1 

样例输出：

25

代码实现： 

#include<iostream>
using namespace std;
int n,m,sx,sy,cx,cy,sum=0;
int mins=2147483647;   //设置最小值 
int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
int G[1001][1001],vis[1001][1001];
void dfs(int x,int y){
	vis[x][y]=1;
	sum+=G[x][y];
	if(x==cx&&y==cy){
		mins=(sum<mins)?sum:mins;  //三目运算，如果总和为最小则更新最小值 
		vis[x][y]=0;//回溯 
		sum-=G[x][y];//及时更新总和的值 
		return;
	}
	for(int i=0;i<4;i++){
		int xx=x+dx[i];   
		int yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0){
			dfs(xx,yy);
		}
	} 
	sum-=G[x][y];  //回溯 
	vis[x][y]=0;  //及时更新总和的值  
	return;
}
int main(){
	cin>>n>>m>>sx>>sy>>cx>>cy;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>G[i][j];
		}
	}
	dfs(sx,sy);
	cout<<mins;
	return 0;
}

题目六：红与黑

问题描述: 

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一
块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多
少块黑色的瓷砖。
输入:第一行是两个整数W和H，分别表示×方向和y方向瓷砖的数量。W和H 都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色
规则如下:

1. '.'黑色的瓷砖；
2. '#'白色的瓷砖；
3. '@’:黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

输出:对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数
时包括初始位置的瓷砖)。

样例输入：

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.	
 
 

样例输入：

45

代码实现： 

#include<iostream>
using namespace std;
int a[1001][1001],book[1001];//a为每件工作的收益值，book为是否被分配工作 
int n;//需要n个人来完成 
int maxl=0; 
int dfs(int step,int t){  //step为第几个工作，t为已得的收益 
	for(int i=1;i<=n;i++){  //表示1-n个人 
		if(!book[i]){
			book[i]=1;
			t+=a[step][i];
			if(step<n) dfs(step+1,t);
			if(t>maxl) maxl=t;//取最大值 
			t-=a[step][i];//回溯 
			book[i]=0;	
		}
	} 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		} 
	}
	dfs(1,0);
	cout<<maxl<<endl;
	return 0;
}

题目七：最多的字母

问题描述：

给出一个R*S的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经出现过的字母。问最多可以经过几个字母。(单次的一条路线不能重复出现相同的字母。) 

样例输入: 

3 6
HFDFFB
AJHFDH
DGAGEH 

样例输出: 

6

问题分析:

代码实现： 

#include<iostream>
using namespace std;
int dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
bool  vis[30]; 
int r,s,sum=1,cnt=1;
char map[1001][1001]; 
int dfs(int x,int y){
	if(cnt>sum) sum=cnt;
	vis[map[x][y]-'A']=1;
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i]; 
		if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&!vis[map[xx][yy]-'A']){
			cnt++;
			dfs(xx,yy);
			vis[map[xx][yy]-'A']=0;
			cnt--;
		}
	}
}
int main(){
	cin>>r>>s;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=s;j++){
			cin>>map[i][j];
		}
	}
	
	dfs(1,1);
	cout<<sum<<endl;
	return 0;
}