Cinte's Leetcode Record
0%

面试题 08.10. 颜色填充

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

面试题 08.10. 颜色填充 - 力扣（LeetCode） (leetcode-cn.com)

dfs

主要是要记录走过的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        dfs(image, image[sr][sc], sr, sc);
        for(auto& line : image)
            for(auto& pi : line)
                if(pi == -1)
                    pi = newColor;
        return image;
    }
private:
    void dfs(vector<vector<int>>& image, int oldColor, int i, int j)
    {
        if(i < 0 || i > image.size() - 1 || j < 0 || j > image[0].size() - 1 || image[i][j] != oldColor)
            return;
        image[i][j] = -1;
        dfs(image, oldColor, i + 1, j);
        dfs(image, oldColor, i - 1, j);
        dfs(image, oldColor, i, j - 1);
        dfs(image, oldColor, i, j + 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        dfs(image, newColor, image[sr][sc], sr, sc);
        return image;
    }
private:
    void dfs(vector<vector<int>>& image, int newColor, int oldColor, int i, int j)
    {
        if(i < 0 || i > image.size() - 1 || j < 0 || j > image[0].size() - 1 || image[i][j] != oldColor || image[i][j] == newColor) // 新旧color如果相同，就没必要走了
            return;
        image[i][j] = newColor;
        dfs(image, newColor, oldColor, i + 1, j);
        dfs(image, newColor, oldColor, i - 1, j);
        dfs(image, newColor, oldColor, i, j - 1);
        dfs(image, newColor, oldColor, i, j + 1);
    }
};
bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(image[sr][sc] == newColor)
            return image;
        queue<pair<int, int>> q;
        q.push(pair<int, int>{sr, sc});
        int oldColor = image[sr][sc];
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            if(p.first < 0 || p.first >= image.size() || p.second < 0 || p.second >= image[0].size() || image[p.first][p.second] != oldColor)
                continue;
            image[p.first][p.second] = newColor;
            q.push({p.first + 1, p.second});
            q.push({p.first - 1, p.second});
            q.push({p.first, p.second + 1});
            q.push({p.first, p.second - 1});
        }
        return image;
    }
};