DFS 和 BFS Flood fill

LeetCode 733 题

其中 DFS 的代码是 https://www.bilibili.com/video/av32546525?t=1643 看大雪菜 up主的视频，因为我 DFS 还不太会用递归的形式

BFS 是自己写的，因为可以套用模板，还是比较容易理解

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
vector<vector<int>> floodFill(vector<vector<int>>&image, int sr, int sc, int newColor)  //DFS
{
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };  // 上右下左
	int oldColor = image[sr][sc];

	if (image.empty() || image[0].empty())
		return image;

	image[sr][sc] = newColor;    // 这一句是改变 image
	for (int i = 0; i < 4; i++)
	{
		int x = sr + dx[i];
		int y = sc + dy[i];

		if (x >= 0 && x < image.size() && y >= 0 && y < image[0].size() && image[x][y] == oldColor)  // 如果下一个是旧颜色就走下去
			floodFill(image, x, y, newColor);
	}
	return image;
}
vector<vector<int>> floodfill(vector<vector<int>>&image, int sr, int sc, int newColor)  // DFS
{
	//  找到各种条件
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };  // 上右下左
	int x = image.size(), y = image[0].size();
	int oldColor = image[sr][sc];

	// 初始化
	image[sr][sc] = newColor;
	stack<pair<int, int>> s;
	pair<int, int>a(sr, sc);
	s.push(a);

	while (!s.empty())   // 开始 
	{
		pair<int, int>vertex = s.top();
		s.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int>next(vertex.first + dx[i], vertex.second + dy[i]);
			if (next.first >= 0 && next.first < x&&next.second >= 0 && next.second < y&&image[next.first][next.second] == oldColor)
			{
				image[next.first][next.second] = newColor;
				s.push(next);
			}
		}

	}
	return image;
}
vector<vector<int>> flood_fill(vector<vector<int>>&image, int sr, int sc, int newColor)
{
	//  找到各种条件
	int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };  // 上右下左
	int x = image.size(), y = image[0].size();
	int oldColor = image[sr][sc];

	// 初始化
	image[sr][sc] = newColor;
	queue<pair<int, int>> q;
	pair<int, int>a(sr, sc);
	q.push(a);

	while (!q.empty())   // 开始 宽搜
	{
		pair<int, int>vertex = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int>next(vertex.first + dx[i], vertex.second + dy[i]);
			if (next.first >= 0 && next.first < x&&next.second >= 0 && next.second < y&&image[next.first][next.second] == oldColor)
			{
				image[next.first][next.second] = newColor;
				q.push(next);
			}
		}
		
	}
	return image;
}

int main(void)
{
	vector<vector<int>>image(100, vector< int>(100,0));  //  初始化 行列 初始值

	int sr = 1, sc = 1, newColor = 2;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			scanf("%d", &image[i][j]);
		}
	}

	image = floodfill(image, sr, sc, newColor);

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			printf("%d ", image[i][j]);
		}puts("");
	}

	system("pause");
	return 0;
}
/*测试数据
1 1 1 1 1 0 1 0 1
*/

　因为是要走遍所有颜色相同且区域相同的地方，所以 BFS 和 DFS 都能遍历

果然还是递归比较方便，因为

① 否则的话就要构造栈或者队列

② 递归的初始化直接在函数调用中就可以实现，而栈或者队列还要另写初始化条件

③ 栈和队列比递归多了一个 while 循环，因为递归本事就是循环。

我的困惑：在递归调用中

为什么最后 image 会变成空的，他又不没有压栈，也没有出栈，为什么递归之后会变空呢？

----- --------------------------------------------------- --

There is no reason to envy someone else's sky because you are a universe

羡慕别人的天空简直没道理因为你就是一座宇宙