首页Coding

# 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 = <!--swig0-->;
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×n)O(m \times n)，其中 mm 和 nn 是二维网格的行数和列数


空间复杂度：O(m×n)O(m \times n)，最坏情况下，递归的深度为 m×nm \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 = <!--swig1-->;
    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×n)O(m \times n)，其中 mm 和 nn 是二维网格的行数和列数


空间复杂度：O(min⁡(m×n))O(\min(m \times n))，在最坏情况下，整个网格均为陆地，队列的大小为 min⁡(m,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≤1 \le  numCourses  ≤2000\le 2000
    • 

  • 0≤0 \le  prerequisites.length  \le 5000$
    • 

  • prerequisites[i].length  == 2
    • 

  • 0≤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)O(n + m)，其中 nn 为课程数（即，numCourses），mm 为先修课程的要求数（即，prerequisites 中一维数组的数量）


空间复杂度：O(n+m)O(n + m)，其中，邻接表所需空间为 O(m)O(m)，队列所需空间为 O(n)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)


空间复杂度：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(ML+Q⋅(L+M))O(M L + Q \cdot (L + M))，其中 MM 为 数组  equations  的长度（边的数量），LL 为字符串的平均长度，QQ 为数组  queries  的长度（查询的数量）


    

  • 构建图时，需要处理 MM 条边，每条边都涉及到 O(L)O(L) 的字符串比较，时间复杂度为 O(ML)O(M L)
    • 

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



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


    

  • 存储每个变量字符串的编号，需要的空间为 O(NL)O(N L)
    • 

  • 存储图中所有的边及其权重，需要的空间为 O(M)O(M)
    • 

  • 广度优先搜索过程中，存放待访问的顶点，需要的空间为 O(N)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≤1 \le  m ,  n  ≤50\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×C)O(R \times C)。其中  R  是给定网格中的行数， C  是列数。访问每个网格最多一次


空间复杂度：O(R×C)O(R \times C)，递归的深度最大可能是整个网格的大小，因此最大可能使用 O(R×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×C)O(R \times C)。其中  R  是给定网格中的行数， C  是列数，访问每个网格最多一次


空间复杂度：O(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≤1 \le  m  ,  n  ≤50\le 50
    • 

  • 0≤0 \le  image[i][j]  ,  newColor  < 2162^{16}
    • 



# 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×m)O(n \times m)，其中  n  和  m  分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。


空间复杂度：O(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×m)O(n \times m)，最坏情况下需要遍历所有的方格一次。


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