###### tags: `Leetcode` `easy` `bfs` `python` `c++`

# 733. Flood Fill

## [題目連結:] https://leetcode.com/problems/flood-fill/description/

## 題目:
An image is represented by an ```m x n``` integer grid ```image``` where ```image[i][j]``` represents the pixel value of the image.

You are also given three integers ```sr, sc, and color```. You should perform a **flood fill** on the image starting from the pixel ```image[sr][sc]```.

To perform a **flood fill**, consider the starting pixel, plus any pixels connected **4-directionally** to the starting pixel of the same color as the starting pixel, plus any pixels connected **4-directionally** to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with ```color```.

Return the modified image after performing the flood fill.


#### [圖片來源:] https://leetcode.com/problems/flood-fill/description/

## 解題想法:
* 題目為，給一matrix image，給定一起始位置(sr,sc)，將周圍與image[sr][sc]同顏色的格都填為color

* 使用bfs
* 從(sr,sc)開始，遍歷四個方位的位置

## Python:

class Solution(object):
    def floodFill(self, image, sr, sc, color):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type color: int
        :rtype: List[List[int]]
        """
        m=len(image)
        n=len(image[0])
        target=image[sr][sc]
        que=[(sr,sc)] #current pos
        visited=set() #already visited
        visited.add((sr,sc))
        dirs=[(1,0),(0,1),(-1,0),(0,-1)] #four dirs
        while que:
            curX,curY=que.pop(0)
            image[curX][curY]=color
            for dirX,dirY in dirs:
                tmpX=curX+dirX
                tmpY=curY+dirY
                if 0<=tmpX<m and 0<=tmpY<n and image[tmpX][tmpY]==target:
                    if (tmpX,tmpY) not in visited:
                        visited.add((tmpX,tmpY))
                        que.append((tmpX,tmpY))
        return image
    
if __name__=='__main__':
    result=Solution()
    ans=result.floodFill(image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2)
    print(ans) #[[2, 2, 2], [2, 2, 0], [2, 0, 1]]

## C++:

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<utility>
using namespace std;

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int m=image.size();
        int n=image[0].size();
        int target=image[sr][sc];
        queue<pair<int,int>> que; //current pos
        //若宣告時設初始 須為queue<pair<int,int>> que{ { {sr,sc} } }
        que.push(make_pair(sr,sc));
        set<pair<int,int>>visited; //already visited
        visited.insert(make_pair(sr,sc));
        vector<vector<int>> dirs={{1,0}, {-1,0}, {0,1}, {0,-1}};
        while (!que.empty()){
            pair<int,int> cur=que.front(); que.pop();
            image[cur.first][cur.second]=color;
            for (auto dir: dirs){
                int tmpX=cur.first+dir[0];
                int tmpY=cur.second+dir[1];
                //不能寫一起判斷 :"( 0<=tmpX<m 會有溢位問題
                if (0<=tmpX && tmpX<m && 0<=tmpY && tmpY<n && image[tmpX][tmpY]==target){
                    if (visited.find({tmpX,tmpY})==visited.end()){
                        visited.insert({tmpX,tmpY});
                        que.push({tmpX,tmpY});
                    }
                }
            }
        }
        return image;
    }
};

int main(){
    vector<vector<int>> image={{1,1,1}, {1,1,0}, {1,0,1} };
    int sr=1, sc=1, color=2;
    Solution res;
    vector<vector<int>> ans=res.floodFill(image,sr,sc,color);
    for (int i=0; i<ans.size(); i++){
        for (int j=0; j<ans[0].size(); j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
/*
2 2 2
2 2 0
2 0 1
*/