深度优先搜索 - 最短路径

刺骨的言语ヽ痛彻心扉 2023-02-10 03:56 171阅读 0赞

#  深度优先搜索 - 最短路径 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

迷宫由 `n` 行 `m` 列的单元格组成 (`n` 和 `m` 都小于等于 50)，每个单元格要么是空地，要么是障碍物。障碍物是不能通行的，要求从迷宫起点开始找到一条通往迷宫中目标位置的最短路径。

使用一个二维数组来存储迷宫，刚开始假设从迷宫入口处 `(1, 1)` 开始，目标位置在 `(ph, qw)`，找到从 `(1, 1)` 到 `(ph, qw)` 的最短路径。如果刚开始在入口的点 `(1, 1)`，那么下一步只能是往右走或者往下走。如果是到了迷宫中间的某个点，那么可能是往上、下、左和右四个方向走，只能一个个去尝试。这里定义一个顺序，按照顺时针的方向逐个尝试 (即按照右、下、左、上的顺序)。

![在这里插入图片描述][20200520000433297.png_pic_center]

从迷宫入口处 `(1, 1)` 开始，一步之内可以达到的点只有 `(1, 2)` 和 `(2, 1)`。根据刚才的策略，我们先往右边走，来到 `(1, 2)` 这个点。来到 `(1, 2)` 之后只能到达 `(2, 2)` 这个点。因为 `(1, 3)` 是障碍物无法到达，`(1, 1)` 是刚才来的路径中已经走过的点，也不能走，所以只能到 `(2, 2)` 这个点。但是目标位置并不在 `(2, 2)` 这个点上，所以还得继续往下走，直至无路可走或者找到目标位置为止。请注意，并不是找到目标位置就结束了。刚才仅仅尝试了一条路，而这条路并不一定是最短的。刚才很多地方在选择方向的时候都有多种选择，因此我们需要返回到这些地方继续尝试往别的方向走，直到把所有可能都尝试一遍，最后输出最短的一条路径。下图就是一种可行的搜索路径。

![在这里插入图片描述][20200520000730292.png_pic_center]

现在尝试用深度优先搜索来解决这个问题，`dfs()` 函数的功能是解决当前应该怎么办。到达某个点的时候需要处理的是：先检查是否已经到达目标位置，如果没有到达则找出下一步可以走的地方。为了解决这个问题，此处 `dfs()` 函数需要维护 4 个参数，分别是地图，当前这个点的 `yh` 坐标、`xw` 坐标以及当前已经走过的步数 `step`。

void dfs(int map_data[50][50], int yh, int xw, int step)
    {
    	return;
    }

判断是否已经到达目标位置很好实现，只需要判断当前的坐标和目标位置的坐标是否相等就可以了，如果相等则表明已经到达目标位置。

void dfs(int map_data[50][50], int yh, int xw, int step)
    {
    	// 判断是否到达目标位置
    	if ((yh == end_yh) && (xw == end_xw))
    	{
    		if (step < min_step) {
    			min_step = step; // 更新最少步骤
    		}
    
    		return; // 返回
    	}
    
    	return;
    }

如果没有到达目标位置，则找出下一步可以走的地方。因为有四个方向可以走，根据我们之前的约定，按照顺时针的方向来尝试 (即按照右、下、左、上的顺序)。为了编程方便，定义了一个方向数组 `next`。

// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };

![在这里插入图片描述][20200520001951337.png_pic_center]

通过这个方向数组，使用循环就很容易获得下一步的坐标。这里将下一步的横坐标用 `txw` 存储，纵坐标用 `tyh` 存储。

// 枚举 4 种走法
    for (int k = 0; k < 4; k++)
    {
    	// 计算下一个点的坐标
    	tyh = yh + next[k][0];
    	txw = xw + next[k][1];
    }

接下来我们就要对下一个点 `(tyh, txw)` 进行判断，包括是否越界，是否为障碍物，以及这个点是否已经在路径中 (即避免重复访问一个点)。需要用 `book[tyh][txw]` 来记录格子 `(tyh, txw)` 是否已经在路径中。

如果这个点符合所有的要求，就对这个点进行下一步的扩展，即 `dfs(map_data, tyh, txw, step + 1);`，注意这里是 `step + 1`，因为一旦你从这个点开始继续往下尝试，就意味着你的步数已经增加了 1。

// 枚举 4 种走法
    	for (int k = 0; k < 4; k++)
    	{
    		// 计算下一个点的坐标
    		tyh = yh + next[k][0];
    		txw = xw + next[k][1];
    
    		// 判断是否越界
    		if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {
    			continue;
    		}
    
    		// 0 表示空地，1 表示障碍物
    		if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    		{
    			book[tyh][txw] = 1; // 标记这个点已经走过
    			dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点
    			book[tyh][txw] = 0; // 尝试结束，取消这个点的标记
    		}
    	}

## 1. D:\\visual\_studio\_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt ##

`input.txt` 第一行是测试用例个数 2，后续依次为具体测试用例数据。  
测试用例第一行有两个数 `YH` 和 `XW`，`YH = 5` 表示迷宫的行数，`XW = 4` 表示迷宫的列数。  
紧接着一行表示起始点坐标 `(start_yh, start_xw)` 和目标位置坐标 `(end_yh, end_xw)`，注意起始点为 `(0, 0)`。  
接下来 `YH = 5` 行 `XW = 4` 列为迷宫地图，`0` 表示空地，`1` 表示障碍物。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

## 2. yongqiang.cpp ##

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int YH = 0, XW = 0;
    int end_yh = 0, end_xw = 0;
    int book[50][50] = { 0 };
    int min_step = INT_MAX;
    
    void dfs(int map_data[50][50], int yh, int xw, int step)
    {
    	// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
    	int tyh = 0, txw = 0;
    
    	// 判断是否到达目标位置
    	if ((yh == end_yh) && (xw == end_xw))
    	{
    		if (step < min_step) {
    			min_step = step; // 更新最少步骤
    		}
    
    		return; // 返回
    	}
    
    	// 枚举 4 种走法
    	for (int k = 0; k < 4; k++)
    	{
    		// 计算下一个点的坐标
    		tyh = yh + next[k][0];
    		txw = xw + next[k][1];
    
    		// 判断是否越界
    		if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {
    			continue;
    		}
    
    		// 0 表示空地，1 表示障碍物
    		if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    		{
    			book[tyh][txw] = 1; // 标记这个点已经走过
    			dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点
    			book[tyh][txw] = 0; // 尝试结束，取消这个点的标记
    		}
    	}
    
    	return;
    }
    
    int inference(int map_data[50][50], int start_yh, int start_xw)
    {
    	int ret = 0;
    
    	// 从起点开始搜索
    	book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走
    	// 第 4 个参数是初始步数 0
    	dfs(map_data, start_yh, start_xw, 0);
    	book[start_yh][start_xw] = 0;
    	ret = min_step;
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num = 0;
    	cin >> case_num;
    	cout << case_num << endl;
    
    	for (int idx = 1; idx <= case_num; idx++)
    	{
    		int start_yh = 0, start_xw = 0;
    
    		// (height, weight)
    		int map_data[50][50] = { 0 };
    
    		cin >> YH >> XW; // initialization
    		cin >> start_yh >> start_xw >> end_yh >> end_xw; // initialization
    
    		cout << YH << XW << endl;
    		cout << start_yh << start_xw << end_yh << end_xw << endl;
    
    		min_step = INT_MAX; // initialization
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cin >> map_data[h][w];
    			}
    		}
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cout << map_data[h][w];
    			}
    			cout << endl;
    		}
    
    		inference(map_data, start_yh, start_xw);
    
    		cout << "CASE #" << idx << " = " << min_step << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int YH = 0, XW = 0;
    int end_yh = 0, end_xw = 0;
    int book[50][50] = { 0 };
    int min_step = INT_MAX;
    
    void dfs(int map_data[50][50], int yh, int xw, int step)
    {
    	// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
    	int tyh = 0, txw = 0;
    
    	// 判断是否到达目标位置
    	if ((yh == end_yh) && (xw == end_xw))
    	{
    		if (step < min_step) {
    			min_step = step; // 更新最少步骤
    		}
    
    		return; // 返回
    	}
    
    	// 枚举 4 种走法
    	for (int k = 0; k < 4; k++)
    	{
    		// 计算下一个点的坐标
    		tyh = yh + next[k][0];
    		txw = xw + next[k][1];
    
    		// 判断是否越界
    		if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {
    			continue;
    		}
    
    		// 0 表示空地，1 表示障碍物
    		if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    		{
    			book[tyh][txw] = 1; // 标记这个点已经走过
    			dfs(map_data, tyh, txw, step + 1); // 开始尝试下一个点
    			book[tyh][txw] = 0; // 尝试结束，取消这个点的标记
    		}
    	}
    
    	return;
    }
    
    int inference(int map_data[50][50], int start_yh, int start_xw)
    {
    	int ret = 0;
    
    	// 从起点开始搜索
    	book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走
    	// 第 4 个参数是初始步数 0
    	dfs(map_data, start_yh, start_xw, 0);
    	book[start_yh][start_xw] = 0;
    	ret = min_step;
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num = 0;
    	cin >> case_num;
    	cout << case_num << endl;
    
    	for (int idx = 1; idx <= case_num; idx++)
    	{
    		int start_yh = 0, start_xw = 0;
    
    		// (height, weight)
    		int map_data[50][50] = { 0 };
    
    		cin >> YH >> XW; // initialization
    		cin >> start_yh >> start_xw >> end_yh >> end_xw; // initialization
    
    		cout << YH << XW << endl;
    		cout << start_yh << start_xw << end_yh << end_xw << endl;
    
    		min_step = INT_MAX; // initialization
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cin >> map_data[h][w];
    			}
    		}
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cout << map_data[h][w];
    			}
    			cout << endl;
    		}
    
    		inference(map_data, start_yh, start_xw);
    
    		cout << "CASE #" << idx << " = " << min_step << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	fclose(stdout);
    
    	return 0;
    }

### 2.1 `D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\output.txt` ###

Start of the program, start = 0
    Start of the program, start = 0
    
    2
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #1 = 7
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #2 = 7
    
    End of the program, end = 1
    End of the program, end = 1
    Total time taken by CPU: 0.001000
    Exiting of the program...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

发明深度优先算法的是 John E.Hopcroft 和 Robert E.Tarjan。1971 ~ 1972 年，他们在斯坦福大学研究图的连通性 (任意两点是否可以相互到达) 和平面性 (图中所有的边相互不交叉。在电路板上设计布线的时候，要求线与线不能交叉，这就是平面性的一个实际应用)，发明了这个算法。他们也因此获得了1986年的图灵奖。

当我们遇到这种需要分身，需要不断尝试完成的事情时，可以尝试使用深度优先搜索算法，要借助计算机的运算速度优势，完成一些生活中比较繁琐重复的事情。

## 3. 注意全局变量初始化 ##

**上面 `2.` 的代码用了太多全局变量是不合适，在运行多个测试用例时，切记不可忘记对全局变量的初始化。**

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int end_yh = 0, end_xw = 0;
    
    void dfs(int map_data[50][50], int yh, int xw, int step, int book[50][50], int YH, int XW, int *min_step)
    {
    	// right, down, left, up - (height, width)
    	int next[4][2] = { { 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
    	int tyh = 0, txw = 0;
    
    	// 判断是否到达目标位置
    	if ((yh == end_yh) && (xw == end_xw))
    	{
    		if (step < *min_step) {
    			*min_step = step; // 更新最少步骤
    		}
    
    		return; // 返回
    	}
    
    	// 枚举 4 种走法
    	for (int k = 0; k < 4; k++)
    	{
    		// 计算下一个点的坐标
    		tyh = yh + next[k][0];
    		txw = xw + next[k][1];
    
    		// 判断是否越界
    		if ((tyh < 0) || (tyh >= YH) || (txw < 0) || (txw >= XW)) {
    			continue;
    		}
    
    		// 0 表示空地，1 表示障碍物
    		if ((0 == map_data[tyh][txw]) && (0 == book[tyh][txw]))
    		{
    			book[tyh][txw] = 1; // 标记这个点已经走过
    			dfs(map_data, tyh, txw, step + 1, book, YH, XW, min_step); // 开始尝试下一个点
    			book[tyh][txw] = 0; // 尝试结束，取消这个点的标记
    		}
    	}
    
    	return;
    }
    
    int inference(int map_data[50][50], int start_yh, int start_xw, int YH, int XW)
    {
    	int ret = 0;
    	int book[50][50] = { 0 };
    	int min_step = INT_MAX;
    
    	// 从起点开始搜索
    	book[start_yh][start_xw] = 1; // 标记起点已经在路径中，防止后面重复走
    	// 第 4 个参数是初始步数 0
    	dfs(map_data, start_yh, start_xw, 0, book, YH, XW, &min_step);
    	book[start_yh][start_xw] = 0;
    	ret = min_step;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num = 0;
    	cin >> case_num;
    	cout << case_num << endl;
    
    	for (int idx = 1; idx <= case_num; idx++)
    	{
    		int start_yh = 0, start_xw = 0;
    		int YH = 0, XW = 0;
    		int ret = 0;
    		// (height, weight)
    		int map_data[50][50] = { 0 };
    
    		cin >> YH >> XW; // initialization
    		cin >> start_yh >> start_xw >> end_yh >> end_xw; // initialization
    
    		cout << YH << XW << endl;
    		cout << start_yh << start_xw << end_yh << end_xw << endl;
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cin >> map_data[h][w];
    			}
    		}
    
    		for (int h = 0; h < YH; h++)
    		{
    			for (int w = 0; w < XW; w++)
    			{
    				cout << map_data[h][w];
    			}
    			cout << endl;
    		}
    
    		ret = inference(map_data, start_yh, start_xw, YH, XW);
    
    		cout << "CASE #" << idx << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

### 3.1 `D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\output.txt` ###

Start of the program, start = 113
    Start of the program, start = 113
    
    2
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #1 = 7
    54
    0032
    0010
    0000
    0010
    0100
    0001
    CASE #2 = 7
    
    End of the program, end = 114
    End of the program, end = 114
    Total time taken by CPU: 0.001000
    Exiting of the program...

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]

## References ##

《啊哈！算法》 - 啊哈磊

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200520000026422.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[20200520000433297.png_pic_center]: https://img-blog.csdnimg.cn/20200520000433297.png#pic_center
[20200520000730292.png_pic_center]: https://img-blog.csdnimg.cn/20200520000730292.png#pic_center
[20200520001951337.png_pic_center]: https://img-blog.csdnimg.cn/20200520001951337.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200519223640369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200520005821274.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200520010114592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2020052021101974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200520211148903.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center