#733. Flood Fill

題目描述

有一張用m x n的整數網格image代表的圖片，其中以image[i][j]表示像素的值。

另外，還會給你三個整數sr、sc和color，你需要從image[sr][sc]為起點開始實現填滿的功能。

填滿指的是從起點的像素開始向上下左右4個方向把和起點像素值相同的像素值用color替換掉。

回傳執行填滿後的圖片。

限制條件

m == image.Length
n == image[i].Length
1 <= m,n <= 50
0 <= image[i][j], color <= 2^16
0 <= sr < m
0 <= sc < n

解題思路

題目的意思簡單來說就是將圖片中的某一個相連起來色塊提換掉，如果有玩過小畫家功能中的填滿，其實就是類似的功能。

首先我們先想像如何在現實中把圖片的某一個色塊給填滿，首先我們會從起點開始，往上下左右尋找相同顏色的像素，尋找的範圍第一不會超過整個色塊的大小，也就是不會超過不同顏色的範圍，第二則是不會超出圖片的邊界。

那找到之後，我們就知道該把哪個色塊中的像素全部上色，完成填滿的功能。

寬度優先搜尋 DFS

public class Solution {
public int[][] FloodFill(int[][] image, int sr, int sc, int color) {		
        //pathfinder
        var points = PathFinder(image,sr,sc);
         foreach(var i in points){
             image[i[0]][i[1]]=color;
         }
        return image;
    }
    public List<int[]> PathFinder(int[][] image, int sr, int sc){
        var l = new List<int[]>();
        int x1=-1,x2=image[0].Length,
            y1=-1,y2=image.Length;        
        int t = image[sr][sc];
        var b = new Queue<int[]>();
        b.Enqueue(new int[2]{sr,sc});
        var passed = new Hashtable();        
        while(b.Count!=0){            
            var p = b.Dequeue();                        
            if(passed.Contains(p[0]+","+p[1])) continue;
            passed.Add(p[0]+","+p[1],1);            
            if(image[p[0]][p[1]]==t) l.Add(p);
            else continue;
            if(p[1]-1>x1 && !passed.Contains(p[0]+","+(p[1]-1))) b.Enqueue(new int[2]{p[0],p[1]-1});
            if(p[1]+1<x2 && !passed.Contains(p[0]+","+(p[1]+1))) b.Enqueue(new int[2]{p[0],p[1]+1});                    
            if(p[0]-1>y1 && !passed.Contains((p[0]-1)+","+p[1])) b.Enqueue(new int[2]{p[0]-1,p[1]});
            if(p[0]+1<y2 && !passed.Contains((p[0]+1)+","+p[1])) b.Enqueue(new int[2]{p[0]+1,p[1]});            
        }
        return l;
    }
}

複雜度分析：

時間複雜度：最差的情況下整張圖都會被檢查過一遍，因此時間上會花費O(m*n)。
空間複雜度：使用了一個List紀錄要修改的點，也使用了一個Queue來規劃檢查路線，另外使用了一個Hashtable來紀錄已經檢查過的像素，
最差的情況下List要記錄所有的點，Queue則是保存了最外圈的路線，而Hashtable則是會記錄m*n-1個點，花費的空間分別為m*n、2m+2n、m*n-1，總共是2mn+2m+2n-1，因此空間複雜度為O(m*n)。

學習重點

寬度優先搜尋DFS的運用。
平面搜尋的策略。