מבול מילוי LeetCode


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית פייסבוק Google
עומק חיפוש ראשון מַטרִיצָה

בבעיית מילוי שיטפון נתנו דו מימד מערך [] [] המייצג תמונה בגודל mxn כאשר כל ערך מייצג את הצבע של הפיקסל באותו קואורדינטה. ניתן גם מיקום או קואורדינטות של פיקסל וצבע. החלף את הצבע במיקום נתון ואת כל הקואורדינטות או המיקומים הסמוכים בצבע זהה למיקום נתון בצבע הנתון. הדפיס את המערך המייצג צבעים חדשים בתמונה.

מבול מילוי LeetCode

דוגמה

עכשיו חפש דוגמאות לאלגוריתם מילוי שיטפון.

קלט:

א [] [] = [[1 1 1]

[1 1 0]

[1 0 1]]

x = 1

y = 1

צבע = 2

פלט: 

[2 2 2]

[2 2 0]

[2 0 1]

קלט:

א [] [] = [[1 1 0]

[1 1 0]

[1 0 0]]

x = 1

y = 3

צבע = 5

פלט:

[1 1 5]

[1 1 5]

[1 5 5]

שיטה רקורסיבית

אלגוריתם למילוי שיטפון LeetCode

  1. אתחל מערך דו-ממדי a [] [] בגודל mxn כאשר m שווה ל- n המייצג תמונה בצורת פיקסלים כאשר כל פיקסל מייצג את צבעו.
  2. אתחל גם שני קואורדינטות x, y וצבע.
  3. אם x ו- y הם פחות מ- 0 או גדולים מ- m או n, חזור.
  4. אחסן את הצבע בקואורדינטות x ו- y במשתנה prevC.
  5. בדוק אם הצבע בקואורדינטות x ו- y אינו שווה ל- prevC כלומר צבע קודם, חזור.
  6. אם הצבע בקואורדינטות x ו- y שווה לצבע חדש, חזור.
  7. אחר כך עדכן את הצבע בקואורדינטות x ו- y כצבע חדש.
  8. בצע ארבע שיחות רקורסיביות לפונקציה עם קואורדינטות כמו (x + 1, y), (x-1, y), (x, y + 1) ו- (x, y-1).
  9. הדפיסו את מערך הדו-ממד המעודכן.

תוכנית C ++ למילוי שיטפון LeetCode

#include<iostream> 
using namespace std; 
  
#define m 3
#define n 3
  
void floodFill(int a[][n], int x, int y, int prevC, int newC){ 
    
    if(x<0 || x>=m || y<0 || y>=n) 
        return; 
    if(a[x][y] != prevC) 
        return; 
    if(a[x][y] == newC)  
        return;  
  
    a[x][y] = newC; 
  
    floodFill(a, x+1, y, prevC, newC); 
    floodFill(a, x-1, y, prevC, newC); 
    floodFill(a, x, y+1, prevC, newC); 
    floodFill(a, x, y-1, prevC, newC); 
} 
  
void Fill(int a[][n], int x, int y, int color){ 
    int prevColor = a[x][y]; 
    floodFill(a, x, y, prevColor, color); 
} 
  
int main(){ 
    
    int a[m][n] = {{1, 1, 1}, 
                   {1, 1, 0}, 
                   {1, 0, 1},
                  }; 
    int x = 1, y = 1, color = 2; 
    
    Fill(a, x, y, color); 
    
    for(int i=0; i<m; i++){ 
        
        cout<<"[ ";
        for (int j=0; j<m; j++) 
           cout<<a[i][j]<<" "; 
        cout<<"]\n"; 
    } 
}
[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]

תוכנית Java למילוי שיטפון LeetCode

class floodfill{ 
  
    static int m = 3; 
    static int n = 3; 
      
    static void floodFill(int a[][], int x, int y, int prevC, int newC){ 
         
        if(x<0 || x>=m || y<0 || y>=n) 
            return; 
        if(a[x][y] != prevC) 
            return; 
      
        a[x][y] = newC; 
      
        floodFill(a, x+1, y, prevC, newC); 
        floodFill(a, x-1, y, prevC, newC); 
        floodFill(a, x, y+1, prevC, newC); 
        floodFill(a, x, y-1, prevC, newC); 
    } 
      
    static void Fill(int a[][], int x, int y, int color){ 
        int prevColor = a[x][y]; 
        floodFill(a, x, y, prevColor, color); 
    } 
      
    public static void main(String[] args){ 
        int a[][] = {{1, 1, 1}, 
                        {1, 1, 0}, 
                        {1, 0, 1}, 
                        }; 
        int x = 1, y = 1, color = 2; 
        Fill(a, x, y, color); 
      
        for(int i=0; i<m; i++){ 
            System.out.print("[ ");
            for(int j=0; j<n; j++) 
                System.out.print(a[i][j]+" "); 
            System.out.print("]");    
            System.out.println(); 
        } 
    } 
}
[ 2 2 2 ]
[ 2 2 0 ]
[ 2 0 1 ]

ניתוח מורכבות למילוי שיטפון LeetCode

מורכבות זמן: O (N) כאשר N הוא מספר האלמנטים השווה לשורה * עמודה. כלומר מספר פיקסלים בתמונות.

מרחב עזר: O (1) מכיוון שאנו לא משתמשים בשום שטח עזר ביישום.

הפניות