# LeetCode 200. 岛屿数量

200. Number of Islands

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

# Method 1: 深度优先搜索

算法思路：

扫描整个二维网格，如果某一个位置为 '1'，则表示查找到一个岛屿，此时需以其为起始位置开始进行深度优先搜索

深度优先搜索的具体操作：

• 将搜索到的 '1' 重新标记为 '0'
• 从该位置出发，向 4 个方向探索与之相连的位置

代码实现：

vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

void helper(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size();
    int n = grid[0].size();
    grid[i][j] = '0'; // 标记 (i, j) 位置，表示已访问过该位置
    for (int k = 0; k < 4; ++k) { // 向四个方向进行搜索
        int newi = i + directions[k][0];
        int newj = j + directions[k][1];
        if (newi >= 0 && newi < m && newj >= 0 && newj < n) {
            if (grid[newi][newj] == '1')
                helper(grid, newi, newj);
        }
    }
}

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    for (int i = 0; i < m; ++i) {    // 遍历起点位置
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') { // 发现一座岛屿
                helper(grid, i, j);  // 扫描整块岛屿
                ++ans;               // 岛屿数量加 1
            }
        }
    }
    return ans;
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 是二维网格的行数和列数

空间复杂度：$O(m \times n)$，最坏情况下，递归的深度为 $m \times n$

# Method 2: 广度优先搜索

算法思路：

扫描整个二维网格，每发现一个位置为 '1'，就表示查找到一个岛屿，将该位置加入队列，针对该岛屿开始广度优先搜索，直到队列为空

• 将搜索到的 '1' 重新标记为 '0'
• 从该位置出发，向 4 个方向探索与之相连的位置

代码实现：

int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int ans = 0;
    vector<vector<int>> directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == '1') {
                ++ans;
                grid[i][j] = '0';
                queue<pair<int, int>> que;
                que.push({i, j});
                while (!que.empty()) {
                    auto neighbor = que.front();
                    que.pop();
                    int x = neighbor.first;
                    int y = neighbor.second;
                    for (int k = 0; k < 4; ++k) {
                        int newx = x + directions[k][0];
                        int newy = y + directions[k][1];
                        if (0 <= newx && newx < m && 0 <= newy && newy < n) {
                            if (grid[newx][newy] == '1') {
                                que.push({newx, newy});
                                grid[newx][newy] = '0';
                            }
                        }
                    }
                }
            }
        }
    }
    return ans;
}

时间复杂度：$O(m \times n)$，其中 $m$ 和 $n$ 是二维网格的行数和列数

空间复杂度：$O(\min(m \times n))$，在最坏情况下，整个网格均为陆地，队列的大小为 $\min(m, n)$

# LeetCode 207. 课程表

207. Course Schedule

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• $1 \le$ numCourses $\le 2000$
• $0 \le$ prerequisites.length \le 5000$
• prerequisites[i].length == 2
• $0 \le$ ai , bi $<$ numCourses
• prerequisites[i] 中的所有课程对 互不相同

# 思路

给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：

• 对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面

那么称该排列是图 G 的 拓扑排序

根据上述定义，有以下结论：

• 如果图 G 中存在环（即图 G 不是 有向无环图 ），图 G 不存在拓扑排序
• 如果图 G 是有向无环图，它的拓扑排序可能不止一种

在本题中，我们可以将每一门课看成一个节点，如果学习课程 A 之前必须完成课程 B，则可以连接一条从 B 到 A 的有向边，然后判断该图是否存在拓扑排序（也就是判断该图是否为有向无环图）

# Method 1: 广度优先遍历

算法思路：

我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）

算法流程：

使用一个队列来进行广度优先搜索：初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且，它们之间的相对顺序是无关紧要的

在广度优先搜索的每一步中，我们取出队首的节点 u：

• 将 u 放入答案数组中

• 移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，就将 v 放入答案数组中

在广度优先搜索的过程结束后，如果答案数组中包含了这 numCourses 个节点，那就说明我们找到了一种拓扑排序，否则，说明图中存在环，也就不存在拓扑排序了

特别地，可以只用一个变量来记录入度为 0 的节点个数，而无需将节点实际放入答案数组中。在广度优先搜索结束后，判断该变量的值是否等于课程数，就能知道是否存在一种拓扑排序

代码实现：

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> edges; // 有向图的边（邻接表）
    vector<int> indeg;         // 节点的入度
    edges.resize(numCourses);
    indeg.resize(numCourses);
    for (auto info : prerequisites) {
        edges[info[1]].push_back(info[0]); // 建立一条从 info[1] 到 info[0] 的有向边
        ++indeg[info[0]];                  // 更新节点 info[0] 的入度
    }

    queue<int> que;  // 存放入度为 0 的节点
    for (int i = 0; i < numCourses; ++i) {
        if (indeg[i] == 0) que.push(i);
    }

    int visited = 0; // 入度为 0 的节点个数（可选修的课程数）
    while (!que.empty()) {
        ++visited;
        int u = que.front();
        que.pop();
        for (int v : edges[u]) { // 移除 u 的所有出边
            --indeg[v];
            if (indeg[v] == 0) que.push(v);
        }
    }
    
    return visited == numCourses;
}

时间复杂度：$O(n + m)$，其中 $n$ 为课程数（即，numCourses），$m$ 为先修课程的要求数（即，prerequisites 中一维数组的数量）

空间复杂度：$O(n + m)$，其中，邻接表所需空间为 $O(m)$，队列所需空间为 $O(n)$

# Method 2: 深度优先搜索

算法思路：

借助一个标志列表 flags，用于判断每个节点 i （课程）的状态

• 未被访问：flags [i] == 0
• 被其他节点启动的深度优先搜索访问过：flags [i] == -1
• 被当前节点启动的深度优先搜索访问过：flags [i] == 1

对 numCourses 个节点依次执行深度优先搜索，判断以每个节点起步的深度优先搜索是否存在环，若存在环直接返回 false

• 终止条件：
  • 当 flag [i] == -1，说明当前访问节点已被其他节点启动的深度优先搜索访问过，无需再重复搜索，直接返回 true
  • 当 flag [i] == 1，说明在本轮深度优先搜索中节点 i 被第 2 次访问，即，有环存在，直接返回 false
• 将当前访问节点 i 对应 flag [i] 置 1
• 递归访问当前节点 i 的所有邻接节点 j，若发现环则直接返回 false
• 当前节点所有邻接节点已被遍历，并没有发现环，将当前节点 flag 置为 -1 并返回 true

待整个图的深度优先搜索结束，如果未发现环，返回 true

代码实现：

vector<vector<int>> edges;
vector<int> flags;

bool DFS(int i) { // 判断是否存在以 i 起始的拓扑排序
    if (flags[i] == -1) return true;
    if (flags[i] == 1) return false;
    flags[i] = 1;
    for (int j : edges[i]) {
        if (DFS(j) == false) return false;
    }
    flags[i] = -1;
    return true;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses);
    flags.resize(numCourses);
    for (auto info : prerequisites) {
        edges[info[1]].push_back(info[0]);
    }
    for (int i = 0; i < numCourses; ++i) {
        if (flags[i] == 0) {
            if (DFS(i) == false) return false;
        }
    }
    return true;
}

时间复杂度：$O(n + m)$

空间复杂度：$O(n + m)$

参考：leetcode-solution

# LeetCode 399. 除法求值

399. Evaluate Division

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意： 输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
    条件：a / b = 2.0, b / c = 3.0
    问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
    结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj 由小写英文字母与数字组成

# Method 1: 广度优先搜索

# 算法思路

可以将整个问题建模成一个图：将变量字符串视为图的顶点，将两个变量的比值视为两顶点之间边的权值，试对任意两点（两个变量）求其路径长度（两个变量的比值）

首先遍历 equations 数组，将每个不同的变量字符串编号，并通过哈希表建立映射

然后，建立每个顶点的边集并将其存储到数组 vector<vector<pair<int, double>>> edges 中，其中， edges[i] 表示第 i 个顶点的边集， edges[i][j].first 表示顶点 i 的第 j 个邻居节点， edges[i][j].second 表示顶点 i 到其第 j 个邻居节点的路径长度（两个变量的比值）

于是，对于任何一个查询，可以从起点出发，通过广度优先搜索的方式，遍历图中的顶点，并更新起点到当前点的路径长度，直到遍历到终点为止

由于每次查询都需要遍历图中的所有顶点，当查询数量较大时，效率就会非常低。因此，可以对图进行预处理，先计算出每个顶点到其他顶点的路径长度，然后再依次处理每一个查询

# 代码实现

vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    // 给变量字符串编号
    int varNum = 0;                  // 变量字符串的数量
    unordered_map<string, int> vars; // 以变量字符串为 key ，以其编号为 value
    for (int i = 0; i < equations.size(); ++i) {
        if (vars.count(equations[i][0]) == 0) {
            vars[equations[i][0]] = varNum;
            varNum++;
        }
        if (vars.count(equations[i][1]) == 0) {
            vars[equations[i][1]] = varNum;
            varNum++;
        }
    }

    // 将变量视为图的顶点，将两个变量的比值视为两顶点之间边的权值
    vector<vector<pair<int, double>>> edges(varNum); // 存储每个点的邻居及其对应的权值
    for (int i = 0; i < equations.size(); ++i) {
        int vertexA = vars[equations[i][0]];
        int vertexB = vars[equations[i][1]];
        edges[vertexA].push_back({vertexB, values[i]});
        edges[vertexB].push_back({vertexA, 1.0 / values[i]});
    }

    vector<double> res;
    for (const auto& q : queries) { // 遍历每一个问题
        // 已知条件中没有出现字符串 q[0] 或 q[1]
        if (vars.count(q[0]) == 0 || vars.count(q[1]) == 0) {
            res.push_back(-1.0);    // 结果为 -1.0
            continue;
        }

        // q[0] 与 q[1] 均出现在已知条件中
        // 采用广度优先搜索
        int vertexA = vars[q[0]];   // 起点的编号
        int vertexB = vars[q[1]];   // 终点的编号
        queue<int> que;             // 队列，存放 待访问的顶点
        que.push(vertexA);          // 将起点入队
        vector<double> ratios(varNum, -1.0); // 存放起点 vertexA 到各顶点的路径长度
        ratios[vertexA] = 1.0;      // vertexA 到其自身的路径长度为 1.0 （自身与自身的比值为 1.0 ）
        while (!que.empty() && ratios[vertexB] < 0) { // 未访问过终点 vertexB
            int u = que.front();    // 当前访问的顶点
            que.pop();              // 将当前顶点出队
            for (const auto [v, val] : edges[u]) { // 处理顶点 u 的每一条边
                if (ratios[v] < 0) {// 未访问过顶点 v 
                    ratios[v] = ratios[u] * val;   // 起点 vertexA 到顶点 v 的路径长度（对应两个变量的比值）
                    que.push(v);    // 将顶点 v 入队
                }
            }
        }
        // 循环结束时，ratios[vertexB] 即为 vertexA 与 vertexB 对应变量的比值
        // 若终点 vertexB 不可达（当队列为空时，仍未访问过 vertexB ），则结果为 -1.0
        res.push_back(ratios[vertexB]);

    }

    return res;
}

其中， ratios[u] 表示 顶点 vertexA 与顶点 u 对应变量的比值， val 表示 顶点 u 与顶点 v 对应变量的比值，因此，顶点 vertex A 与顶点 v 对应变量的比值为 ratios[u] * val ，即， ratios[v] = ratios[u] * val

# 复杂度分析

时间复杂度：$O(M L + Q \cdot (L + M))$，其中 $M$ 为 数组 equations 的长度（边的数量），$L$ 为字符串的平均长度，$Q$ 为数组 queries 的长度（查询的数量）

• 构建图时，需要处理 $M$ 条边，每条边都涉及到 $O(L)$ 的字符串比较，时间复杂度为 $O(M L)$
• 处理每次查询时都要进行一次 $O(L)$ 的字符串比较、遍历 $O(M)$ 条边（最坏情况下），时间复杂度为 $O((L + M) \cdot Q)$

空间复杂度：$O(N L + M)$，其中 $N$ 为数组 equations 中的字符串的种类数（图的顶点个数）

• 存储每个变量字符串的编号，需要的空间为 $O(N L)$
• 存储图中所有的边及其权重，需要的空间为 $O(M)$
• 广度优先搜索过程中，存放待访问的顶点，需要的空间为 $O(N)$

# Method 2: 带权并查集

参考：leetcode-solution

# LeetCode 695. 岛屿的最大面积

LeetCode 695. Max Area of Island

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0 （代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6

示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0

提示：

• m == grid.length
• n == grid[i].length
• $1 \le$ m , n $\le 50$
• grid[i][j] 为 0 或 1

# Method 1: 深度优先搜索

计算网格中每个连通形状的面积，然后取最大值。

在一个土地上，向 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积

为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0

private:
    int DFS(vector<vector<int>>& grid, int cur_i, int cur_j) {  // 深度优先搜索
        if (cur_i < 0 || cur_i == grid.size() || cur_j < 0 || cur_j == grid[0].size() || grid[cur_i][cur_j] == 0) return 0;                       // cur_i cur_j 超出边界或grid[cur_i][cur_j]为0时，返回0
        grid[cur_i][cur_j] = 0; // 已经访问过的位置置0，以免重复访问
        int ans = 1;            // 岛屿面积
        const int di[4] = {-1,1,0,0};
        const int dj[4] = {0,0,-1,1};
        for (int index = 0; index < 4; index++) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += DFS(grid,next_i,next_j);
        }
        return ans;
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++)
            for (int j = 0; j< grid[0].size(); j++)
                ans = max(ans, DFS(grid,i,j));
        return ans;
    }

时间复杂度：$O(R \times C)$。其中 R 是给定网格中的行数， C 是列数。访问每个网格最多一次

空间复杂度：$O(R \times C)$，递归的深度最大可能是整个网格的大小，因此最大可能使用 $O(R \times C)$ 的栈空间

# Method 2: 深度优先搜索 + 栈

# Method 3: 广度优先搜索

把方法二中的栈改为队列，每次从队首取出土地，并将接下来想要遍历的土地放在队尾，就实现了广度优先搜索算法

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int ans = 0;
    for (int i = 0; i != grid.size(); ++i) {
        for (int j = 0; j != grid[0].size(); ++j) {
            int cur = 0;
            queue<int> queuei;
            queue<int> queuej;
            queuei.push(i);
            queuej.push(j);
            while (!queuei.empty()) {
                int cur_i = queuei.front(), cur_j = queuej.front();
                queuei.pop();
                queuej.pop();
                if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {
                    continue;
                }
                ++cur;
                grid[cur_i][cur_j] = 0;
                int di[4] = {0, 0, 1, -1};
                int dj[4] = {1, -1, 0, 0};
                for (int index = 0; index != 4; ++index) {
                    int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                    queuei.push(next_i);
                    queuej.push(next_j);
                }
            }
            ans = max(ans, cur);
        }
    }
}

时间复杂度：$O(R \times C)$。其中 R 是给定网格中的行数， C 是列数，访问每个网格最多一次

空间复杂度：$O(R \times C)$，队列中最多会存放所有的土地，土地的数量最多为 R × C 块

# LeetCode 733. 图像渲染

LeetCode 733. Flood Fill

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小（索引 i 和 j 均从 0 开始）。

你也被给予三个整数 sr ， sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 。

示例 1：

输入：image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
输出：[[2,2,2],[2,2,0],[2,0,1]]
解释：在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2：

输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出：[[2,2,2],[2,2,2]]

提示：

• m == image.length
• n == image[i].length
• $1 \le$ m , n $\le 50$
• $0 \le$ image[i][j] , newColor < 2^

# Method 1: 广度优先搜索

每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。

注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。

注意：当目标颜色和初始颜色相同时，我们无需对原数组进行修改。

const int dx[4] = {1, 0, 0, -1};                // 四个方向
const int dy[4] = {0, 1, -1, 0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int currColor = image[sr][sc];
    if (currColor == newColor) return image;    // 目标颜色和初始颜色相同
    int n = image.size(), m = image[0].size();
    queue<pair<int, int>> que;                  // 待搜索位置的队列
    que.emplace(sr, sc);                        // 初始化
    image[sr][sc] = newColor;
    while (!que.empty()) {
        int x = que.front().first, y = que.front().second;
        que.pop();
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i], my = y + dy[i];
            if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                que.emplace(mx, my);
                image[mx][my] = newColor;
            }
        }
    }
    return image;

时间复杂度：$O(n \times m)$，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。

空间复杂度：$O(n \times m)$，主要为队列的开销。

# Method 2: 深度优先搜索

从给定的起点开始，进行深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的颜色更新，以防止重复搜索；如果不相同，则进行回溯。

const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
void dfs(vector<vector<int>>& image, int x, int y, int color, int newColor) {
    if (image[x][y] == color) {
        image[x][y] = newColor;
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i], my = y + dy[i];
            if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()) {
                dfs(image, mx, my, color, newColor);    // 递归，深度优先搜索
            }
        }
    }
}

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
    int currColor = image[sr][sc];
    if (currColor != newColor) {
        dfs(image, sr, sc, currColor, newColor);
    }
    return image;
}

时间复杂度：$O(n \times m)$，最坏情况下需要遍历所有的方格一次。

空间复杂度：$O(n \times m)$，主要为栈空间的开销。