홍수 채우기 LeetCode


난이도 쉽게
자주 묻는 질문 아마존 페이스북 서비스 구글
깊이 우선 검색 매트릭스

홍수 채우기 문제에서 우리는 2D 정렬 a [] []는 mxn 크기의 이미지를 나타내고 각 값은 해당 좌표에서 픽셀의 색상을 나타냅니다. 또한 픽셀과 색상의 위치 또는 좌표가 주어집니다. 주어진 위치와 모든 인접 좌표 또는 위치의 색상을 주어진 위치와 동일한 색상으로 지정된 색상으로 바꿉니다. 이미지의 새로운 색상을 나타내는 배열을 인쇄합니다.

홍수 채우기 LeetCode

이제 홍수 채우기 알고리즘의 예를 살펴 보겠습니다.

입력 :

a [] [] = [[1 1 1]

[1 1 0]

[1 0 1]]

X = 1

y = 1

색상 = 2

출력 : 

[2 2 2]

[2 2 0]

[2 0 1]

입력 :

a [] [] = [[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. mxn 크기의 2D 배열 a [] []를 초기화합니다. 여기서 m은 이미지를 픽셀 형태로 나타내는 n과 같으며 각 픽셀은 색상을 나타냅니다.
  2. 또한 두 개의 좌표 x, y 및 색상을 초기화하십시오.
  3. x와 y가 0보다 작거나 m 또는 n보다 크면 반환합니다.
  4. 변수 prevC의 좌표 x 및 y에 색상을 저장합니다.
  5. 좌표 x와 y의 색상이 이전 색상, 즉 이전 색상과 같지 않은지 확인합니다.
  6. 좌표 x 및 y의 색상이 새 색상과 같으면 반환합니다.
  7. 그렇지 않으면 좌표 x 및 y의 색상을 새 색상으로 업데이트하십시오.
  8. (x + 1, y), (x-1, y), (x, y + 1) 및 (x, y-1)과 같은 좌표를 사용하여 함수를 XNUMX 번 반복 호출합니다.
  9. 업데이트 된 2D 배열을 인쇄합니다.

홍수 채우기 LeetCode를위한 C ++ 프로그램

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

홍수 채우기 LeetCode 용 Java 프로그램

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은 Row * Column과 같은 요소의 수입니다. 즉, 숫자 이미지 픽셀.

보조 공간 : O (1) 구현시 보조 공간을 사용하지 않기 때문입니다.

참조