1

## 【小馬的LeetCode練功坊】733. Flood Fill (Easy)

(註: 座標從0開始算)

``````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]]
``````

# c++解法一:

``````class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {

int R = image.size(), C = image[0].size();

int oldColor = image[sr][sc];
if(oldColor==newColor){
return image;
}

image[sr][sc] = newColor;
if(sr+1<R && image[sr+1][sc]==oldColor)
floodFill(image,sr+1,sc, newColor);
if(sr-1>=0 && image[sr-1][sc]==oldColor)
floodFill(image,sr-1,sc, newColor);
if(sc+1<C && image[sr][sc+1]==oldColor)
floodFill(image,sr,sc+1, newColor);
if(sc-1>=0 && image[sr][sc-1]==oldColor)
floodFill(image,sr,sc-1, newColor);
return image;

}
};
``````

# c++解法二:

``````class Solution {
public:

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
{
int R = image.size(), C = image[0].size();
int oldColor = image[sr][sc];
if(oldColor==newColor){
return image;
}
image[sr][sc] = newColor; //塗色

vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
for(auto d: directions){
int r = sr+d.first, c = sc+d.second;
if(r<R && r>=0 && c<C && c>=0 && image[r][c]==oldColor){
floodFill(image,r,c, newColor);
}
}
return image;
}

};
``````

# 類似題- 200. Number of Islands

LeetCode上的第200題要數島嶼的個數，

## c++程式解

``````template <typename T>
void floodFill(vector<vector<T>>& image, int sr, int sc, T newColor)
{
int R = image.size(), C = image[0].size();
T oldColor = image[sr][sc];
if(oldColor==newColor){
return;
}
image[sr][sc] = newColor; //塗色

vector<pair<int, int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}}; //定義四個方向
for(auto d: directions){
int r = sr+d.first, c = sc+d.second;
if(r<R && r>=0 && c<C && c>=0 && image[r][c]==oldColor){
floodFill(image,r,c, newColor);
}
}
}

class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int cnt = 0; //計算島嶼數量
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++){
if(grid[i][j]=='1'){
cnt++;
floodFill(grid, i, j, '0');
}
}
}
return cnt;
}
};
``````