733.图像渲染

两天宇宙人

2020-02-17

非递归实现

类似岛屿数量这个题目。

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        stack<pair<int, int>> stk;
        set<pair<int, int>> st;
        st.insert({sr, sc});
        stk.push({sr,sc});
        int smc = image[sr][sc];
        image[sr][sc] = newColor;
        while(stk.size()) {
            auto p = stk.top();
            // cout << 1<< endl;
            stk.pop();
            int i = p.first, j = p.second;
            if(i - 1>= 0 && image[i - 1][j] == smc && !st.count({i - 1, j})){
                image[i - 1][j] = newColor;
                stk.push({i - 1, j});
                st.insert({i - 1, j});
            } 
            if(j + 1 < image[0].size() && image[i][j + 1] == smc && !st.count({i, j + 1})) {
                image[i][j + 1] = newColor;
                stk.push({i, j + 1});
                st.insert({i, j + 1});
            }
            if(1 + i < image.size() && image[i + 1][j ] == smc && !st.count({i + 1, j})) {
                image[i + 1][j ] = newColor;
                stk.push({i + 1, j});
                st.insert({i + 1, j});
            }
            if(j - 1 >=0 && image[i][j - 1] == smc && !st.count({i, j - 1})){
                image[i][j - 1] = newColor;
                stk.push({i, j - 1});
                st.insert({i, j - 1});
            }
        }
        return image;
    }
};