QeuroIzoのBlog

hello world

0%

33. 图像渲染

发表于

题目

解析

  • DFS

    1. 首先判断是否为image是否为空，如果是，则返回image
    2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
    3. 接着，对周围的这些点进行遍历，符合条件的，进入递归
    4. 最后，返回image

  • BFS

    1. 首先判断是否为image是否为空，如果是，则返回image
    2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
    3. 创建队列，类型为 pair<int, int> 类型，将image[sr][sc]入队；
    4. 对队列 q 进行遍历，将 q.front() 变为 newColor，然后，遍历周围的点，符合条件的入队
    5. 最后，返回image

代码

  • DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor)
        return image;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    image[sr][sc] = newColor;
    for(int i = 0; i < 4; i++) {
        int nSr = sr + next[i][0], nSc = sc + next[i][1];
        if(nSr >= 0 && nSr < image.size() && nSc >= 0 && nSc < image[0].size() && image[nSr][nSc] == old)
            floodFill(image, nSr, nSc, newColor);
    }
    return image;
}

  • BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor) {
        return image;
    }
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    queue<pair<int, int> > q;
    q.push(pair<int, int>(sr, sc));
    while(q.size()) {
        pair<int, int> t = q.front();
        q.pop();
        image[t.first][t.second] = newColor;
        for(int i = 0; i < 4; i++) {
            int nx = t.first + next[i][0], ny = t.second + next[i][1];
            if(nx >= 0 && nx < image.size() && ny >= 0 && ny < image[0].size() && image[nx][ny] == old) {
                q.push(pair<int, int>(nx, ny));
            }
        }
    }
    return image;
}