[数据结构与算法]深度优先搜索- -简单版

在图上寻找路径

int main() {
?? ?//将所有点都标记为新点;
?? ?//起点 = 1;
?? ?//终点 = 8;
?? ?cout << Dfs(起点);
}

判断从V出发能否找到终点

bool Dfs(V) {//从V出发判断是否能到终点
	if (V是终点)
		return true;
	if (V是旧点)
		return false;
	将V标记为旧点
	对和V相邻的每个节点U{
		if (Dfs(U) == true)
			return true;
		}
	 return false;
}

判断从V出发能否走到终点，如果能，要记录路径

Node path[MAX_LEN];//MAX_LEN取节点总数即可
int depth;
bool Dfs(V) {//从V出发进行遍历
	if (V是终点) {
		path[depth] = V;
		return true;
	}
	if (V是旧点) {
		return false;
	}
	将V标记为旧点;
	path[depth] = V;
	depth++;
	对和V相邻的每个节点U{
		if (Dfs(U) == true)
		return 0;
	}
	--depth;
	return false;
}
int main() {
	将所有点标记为新点;
	depth = 0;
	if (Dfs(起点)) {
		for (int i = 0; i <= depth; i++)
			cout << path[i] << endl;
	}
}

遍历图上所有节点

Dfs(V) {//从V出发进行遍历
	if (V是旧点) {
		return;
	}
	将V标记为旧点;
	对和V相邻的每个点U{
		Dfs(U);
	}
}
int main() {
	将所有点都标记为新点;
	while (在图中能找到新点k) {
		Dfs(k);
	}
}

邻接矩阵

G[i][j]可以是自定义类型，可以是int,也可以是struct?

?邻接表

?城堡问题

1817:城堡问题??????

总时间限制:?

1000ms

内存限制:?

65536kB

描述

     1   2   3   4   5   6   7  
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################
           (图 1)

   #  = Wall   
   |  = No wall
   -  = No wall

图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成m?n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。

输入

程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。

输出

城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。

样例输入

4 
7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13 

样例输出

5
9

?思路：西墙1 ：1；北墙2：10；东墙4：100；南墙8：1000.

每个方块有几面墙，二进制数位运算。

方块看作节点，相邻方块之间没有墙，则视为有边相连。房间数：所有极大连通子图数目；最大房间：所有极大连通子图中节点最多的那个

?对每一个房间，进行深搜，可以得到该节点所在的极大连通子图。房间数目- -染色，用的颜色种类

#include <iostream>
using namespace std;
int R, C;//行列数
int rooms[60][60];//存储图的信息
int color[60][60];//方块是否染过色的标记 标记
int maxRoomArea = 0, roomNum = 0;//最大的面积，房间数目
int roomArea;//正在探索的连通子图面积
void Dfs(int i, int k) {
	//从节点(i,k)出发，进行深度优先搜索
	//即搜素该节点所在的极大连通子图
	if (color[i][k])//递归结束
		return;
	roomArea++;//该方块加入房间，面积加1
	color[i][k] = roomNum;
	//对和(i,j)节点相邻的节点进行深搜
	//西墙1 ：1；北墙2：10；东墙4：100；南墙8：1000
	if ((rooms[i][k] & 1) == 0&&k-1>=1)//向西走且不出界
		Dfs(i, k - 1);
	if ((rooms[i][k] & 2) == 0&&i-1>=1)//向北走且不出界
		Dfs(i - 1, k);
	if ((rooms[i][k] & 4) == 0&&k+1<=C)//向东走且不出界
		Dfs(i, k + 1);
	if ((rooms[i][k] & 8) == 0&&i+1<=R)//向南走且不出界
		Dfs(i + 1, k);
}
int main() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++)
		for (int k = 1; k <= C; k++)
			cin >> rooms[i][k];
	memset(color, 0, sizeof(color));//所有点都标记为新点
	for (int i = 1; i <= R; i++)
		for (int k = 1; k <= C; k++) {//循环遍历所有的点
			if (!color[i][k]) {//没有染色标记- - 在图中能找到新点
				roomNum++;//找到了新的极大连通子图-新房间
				roomArea = 0;
				Dfs(i, k);//深搜
				maxRoomArea =
					max(roomArea, maxRoomArea);
			}
		}
	cout << roomNum << endl;
	cout << maxRoomArea << endl;
	//复杂度 O(R*C)
}

?踩方格

有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：

a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；

请问：如果允许在方格矩阵上走?n?步，共有多少种不同的方案。

2?种走法只要有一步不一样，即被认为是不同的方案。

输入格式

允许在方格上行走的步数?n(n≤20)。

输出格式

计算出的方案数量。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

2

样例输出

7

思路：

递归-- - 分类讨论

从(i,j)出发，走n步的方案数，等于以下三项的和：

1）下一步向北走，走到(i-1,j)，然后从(i-1,j)走n-1步的方案数；前提(i-1,j)还没有走过

2）下一步向东走，走到(i,j+1)，然后从(i,j+1)走n-1步的方案数；前提(i,j+1)还没有走过

3）下一步向西走，走到(i,j-1)，然后从(i,j-1)走n-1步的方案数 。前提(i,j-1)还没有走过

再分析- - 深度优先搜索

从(i,j)出发，走n步的方案数（从(i,j)出发遍历），等于以下三项的和：

1）下一步向北走，走到(i-1,j)，然后从(i-1,j)走n-1步的方案数；前提(i-1,j)还没有走过- - 相邻的新点

2）下一步向东走，走到(i,j+1)，然后从(i,j+1)走n-1步的方案数；前提(i,j+1)还没有走过- - 相邻的新点

3）下一步向西走，走到(i,j-1)，然后从(i,j-1)走n-1步的方案数 。前提(i,j-1)还没有走过- - 相邻的新点

递归边界： n等于0时，从(i,j)出发，走0步的方案数只有一种，就是走0步

?

#include <iostream>
using namespace std;
int visited[100][100];
int ways(int i, int j, int n) {
	//从点(i,j)出发，走n步的方案数- - 从某节点出发，遍历
	if (n == 0)
		return 1;
	visited[i][j] = 1;//标记为旧点
	int num = 0;
	if (!visited[i][j - 1])//向西走
		num += ways(i, j - 1, n - 1);
	if (!visited[i][j + 1])//向东走
		num += ways(i, j + 1, n - 1); 
	if (!visited[i - 1][j])//向北走
		num += ways(i - 1, j, n - 1);
	//以上求出了在先从(i,j)走的情况下，所有的情况
	//既然已经求出了这个num了，我们就应该撤去对(i,j)的标记
	//先走(m,n)的情况下，还可以再走(i,j),
	//前提是，在走(m,n)之前，没有走过(i,j)
	visited[i][j] = 0;//
	return num;
}
int main() {
	int n;
	cin >> n;
	//全部置为新点
	memset(visited, 0, sizeof(visited));

	//平面无限大，可以任选起点，
	//从(25,25)出发，走不超过20步不越界- - 省去判断
	cout << ways(25, 25, n) << endl;
	return 0;
}

一个状态，相当于图上的一个节点，(i,j,n)节点，与状态(i,j,n)相邻的状态是(i-1,j,n-1)、(i,j-1,n-1)、(i,j+1,n-1)，相邻表示有边。

在一个图上，从节点(x,y,n)出发，其中x,y任选，n是20，走到一些目标节点(x1,y1,0)，求一共有多少种走法。深搜，从图上的节点出发（某个状态），走到某个目标节点或者某些目标节点（某个或者某些状态），求解一共有多少种走法，或者最近路径，或者权值最小，等等。