数据结构之BFS广度优先算法（腐烂的苹果）

队列这个数据结构在很多场景下都有使用，比如在实现二叉树的层序遍历，floodfill问题(等等未完成)中，都需要借助队列的先进先出特性，下面给出这几个问题的解法

经典的二叉树的层序遍历

算法图示，以下图所示的二叉树为例

二叉树层序遍历 C++代码实现

typedef struct binaryTreeNode {struct binaryTreeNode* left;struct binaryTreeNode* right;BTDataType data;
}BTNode;void levelOrder(BTNode* root)
{std::queue<BTNode*> nodeQ;if (root){nodeQ.push(root);}while (!nodeQ.empty()){BTNode* front = nodeQ.front();std::cout << front->data;if (front->left){nodeQ.push(front->left);}if (front->right){nodeQ.push(front->right);}nodeQ.pop();}
}

 注意：队列中存放的是二叉树中结点的指针，每次都去找队列的头部元素，通过头部元素找到其非空的左右孩子，并把头部元素出队列，此时出队列得到的序列就是二叉树的层序遍历序列

Floodfill问题之腐烂的苹果

（牛客网链接：腐烂的苹果_牛客题霸_牛客网 (nowcoder.com)）

Flood Fill（泛洪填充）算法是一种图像处理的基本算法，用于填充连通区域。该算法通常从一个种子点开始，沿着种子点的相邻像素进行填充，直到遇到边界或者其他指定的条件为止。

如果用BFS的思想来解决这个问题，每次循环都只考虑队列中头元素的上下左右

需要考虑的有：

        1. 查看上下左右元素时不能发生越界

        2. 只将上下左右元素中为 1 的那些元素的二维坐标位置放到队列中

        3. 放到队列中的二维坐标位置设置为 true

           

代码实现 

int rotApple(vector<vector<int> >& grid) {int upanddown[4] = {0, 0, -1, 1};int leftandright[4] = {-1, 1, 0, 0};bool vis[1010][1010] = {false};int n = grid.size();int m = grid[0].size();queue<pair<int, int>> findtwoq;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 2) {findtwoq.push({i, j});}}}int ret = 0;while (findtwoq.size()) {int sz = findtwoq.size();ret++;while (sz--) {auto [a, b] = findtwoq.front();findtwoq.pop();for (int i = 0; i < 4; i++) {int x = a + upanddown[i], y = b + leftandright[i];if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y]){vis[x][y] = true;findtwoq.push({x, y});}}}}for(int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1 && vis[i][j] == false) {return -1;}}}return ret - 1;
}