홍수 채우기 알고리즘

<시간/>

이 문제에서는 2차원 화면을 나타내는 2차원 배열, 색으로 채울 화면의 픽셀 좌표 및 색이 제공됩니다. 우리의 임무는 현재 픽셀과 해당 색상을 가진 모든 인접 픽셀에 색상을 지정하는 프로그램을 만드는 것입니다.

페인트 채색 , 색상을 선택하고 주어진 픽셀을 브러시로 클릭합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력:화면[][] ={{W, W, B, W, W, W, W, W},{W, W, W, W, W, W, B, B},{W , B, B, W, W, B, W, W},{W, Y, Y, Y, Y, B, W, B},{B, W, W, Y, Y, B, W, B },{B, W, W, Y, Y, Y, Y, B},{W, B, W, W, W, Y, W, W},{W, W, B, B, W, Y , Y, W}};X =5, Y =5, newColor =R.출력:{{W, W, B, W, W, W, W, W},{W, W, W, W, W , W, B, B},{W, B, B, W, W, B, W, W},{W, R, R, R, R, B, W, B},{B, W, W , R, R, B, W, B},{B, W, W, R, R, R, R, B},{W, B, W, W, W, R, W, W},{W , W, B, B, W, R, R, W}};

이 알고리즘에서 픽셀은 이미 선택된 이전 색상에 있을 때 새 색상으로 채워집니다. 이전 색상이 이전 색상이 아니면 해당 픽셀이 채워지지 않습니다. 픽셀을 채운 후 위, 아래, 왼쪽 및 오른쪽 픽셀이 동일한 작업을 수행하는지 확인합니다. 여기에서 자세히 알아보세요.

해결 방법

문제를 해결하는 한 가지 방법은 재귀 접근 방식을 사용하는 것입니다. 색상을 지정해야 하는 첫 번째 pinel을 찾은 다음 4개의 인접 픽셀을 모두 확인합니다. 같은 색상을 맞춘 다음 새 색상으로 교체하고 현재 픽셀의 이웃과 반복합니다. 인접 픽셀의 색상이 다른 경우 그대로 두십시오. 시작 픽셀과 동일한 색상을 가진 모든 인접한 pinel이 색상이 지정될 때까지 다음 단계를 따르십시오. 그런 다음 채우기 알고리즘을 중지합니다.

예

솔루션 작동을 설명하는 프로그램

#includenamespace std;#define M 8#define N 8void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){ if (x <0 || x>=M || y <0 || y>=N) 반환; if (screen[x][y] !=oldColor) return; if (화면[x][y] ==색상) return; 화면[x][y] =색상; fillColorAdj(화면, x+1, y, oldColor, 색상); fillColorAdj(화면, x-1, y, oldColor, 색상); fillColorAdj(화면, x, y+1, oldColor, 색상); fillColorAdj(screen, x, y-1, oldColor, color);}void fillColor(char screen[][N], int x, int y, char color){ char oldColor =screen[x][y]; if(oldColor==색상) 반환; fillColorAdj(화면, x, y, oldColor, 색상);}int main(){ 문자 화면[M][N] ={{'W', 'W', 'B', 'W', 'W', 'W', 'W', 'W'}, {'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B'}, {'W ', 'B', 'B', 'W', 'W', 'B', 'W', 'W'}, {'W', 'Y', 'Y', 'Y', 'Y ', 'B', 'W', 'B'}, {'B', 'W', 'W', 'Y', 'Y', 'B', 'W', 'B'}, { 'B', 'W', 'W', 'Y', 'Y', 'Y', 'Y', 'B'}, {'W', 'B', 'W', 'W', 'W', 'Y', 'W', 'W'}, {'W', 'W', 'B', 'B', 'W', 'Y', 'Y', 'W'} ,}; 정수 x =5, y =5; 문자 색상 ='R'; cout<<"초기 화면 좌표는 다음과 같습니다. \n"; for (int i=0; i 출력
  초기 화면의 좌표,는 :염색 후의 W W B W W W W WW W W W W W B BW B B W W B W WW Y Y Y Y B W BB W W Y Y B W BB W W Y Y Y Y BW B W W W Y W WW W B B W Y Y WThe 스크린 좌표,는 :W W B W W W W WW W W W W W B BW B B W W B W WW R R R R B W BB W W R R B W BB W W R R R R BW B W W W R W WW W B B W R R W