iT邦幫忙

1

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

參考題目: leetCode- 733. Flood Fill

題目: 給你一個二維陣列,往指定位置(sr, sc)倒入新顏色,相鄰相同顏色的格子都會變成新顏色
(註: 座標從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++解法二:

但是上述解法有個問題,
在判斷條件上有點繁鎖,容易寫錯,
其實可以定義四個相鄰方向的向量,
再用for迴圈對四個方向做一樣的判斷,
避免重複的程式碼,
修改如下:

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. Number of Islands

LeetCode上的第200題要數島嶼的個數,
與上面的733題是非常類似的題目,
將島嶼塗上水的顏色就是答案了

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;
    }
};

尚未有邦友留言

立即登入留言