Leetcode:733. image rendering [BFS]

Title Description

There's a picture m x n A picture represented by a two-dimensional array of integers image , among image[i][j] Indicates the pixel value size of the picture .

You are also given three integers sr , sc and newColor . You should start with pixels image[sr][sc] Start editing the image Color fill .

In order to complete the Coloring work , Start with the initial pixel , Record the initial coordinates Up, down, left and right Connected pixels with the same pixel value as the initial coordinates , Then record the pixels that meet the conditions in these four directions and correspond to them In four directions Connected pixels with the same pixel value as the initial coordinates ,……, Repeat the process . Change the color value of all recorded pixels to newColor .

Finally back to The color rendered image .

Input and output

Input : image = [[1,1,1],[1,1,0],[1,0,1]],sr = 1, sc = 1, newColor = 2
Output : [[2,2,2],[2,2,0],[2,0,1]]

Tips

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], newColor < 216
• 0 <= sr < m
• 0 <= sc < n

Ideas

The meaning of the title is to find [sr][sc] Connected block as the starting point , Change its value to newColor. use bfs Just do it .

AC Code

class Solution {
    
public:
    int dir[4][2] = {
    {
    1, 0}, {
    0, 1}, {
    0, -1}, {
    -1, 0}};
    int vis[50][50];
    typedef pair<int, int> pii;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    
        queue<pii> q;
        int val = image[sr][sc];
        int n = image.size();
        int m = image[0].size();
        q.push(pii(sr, sc));
        while(!q.empty()) {
    
            pii cur = q.front(); q.pop();
            int cx = cur.first, cy = cur.second;
            image[cx][cy] = color;
            vis[cx][cy] = 1;
            for (int i = 0; i < 4; ++i) {
    
                int dx = cx + dir[i][0];
                int dy = cy + dir[i][1];
                if (dx < 0 || dx >= n || dy < 0 || dy >= m || image[dx][dy] != val || vis[dx][dy] == 1) continue;
                q.push(pii(dx, dy));
            }
        }
        return image;
    }
};