홍수 채우기 알고리즘

하나의 행렬이 제공됩니다. 매트릭스는 한 화면을 나타냅니다. 화면의 각 요소(i, j)는 픽셀로 표시되며 해당 픽셀의 색상은 다른 숫자로 표시됩니다. 이 알고리즘에서 픽셀은 이미 선택된 이전 색상에 있을 때 새 색상으로 채워집니다. 이전 색상이 이전 색상이 아니면 해당 픽셀이 채워지지 않습니다. 픽셀을 채운 후 위, 아래, 왼쪽 및 오른쪽 픽셀이 동일한 작업을 수행하는지 확인합니다.

아이디어는 정말 간단합니다. 먼저 선택한 위치가 이전 색상으로 색칠되어 있는지 여부를 확인합니다. 그렇지 않으면 알고리즘이 작동하지 않습니다. 그렇지 않으면 해당 픽셀을 새 색상으로 채우고 4개의 이웃에 대해 반복합니다.

입력 및 출력

입력:화면 행렬:1 1 1 1 1 1 1 11 1 1 1 1 1 0 01 0 0 1 1 0 1 11 2 2 2 2 0 1 01 1 1 2 2 0 1 01 1 1 2 2 2 2 01 1 1 1 1 2 1 11 1 1 1 1 2 2 1출력:범람 채우기 후 화면 행렬1 1 1 1 1 1 1 11 1 1 1 1 1 0 01 0 0 1 1 0 1 11 3 0 3 1 3 01 3 1 1 3 3 0 1 01 1 1 3 3 3 3 01 1 1 1 1 3 1 11 1 1 1 1 3 3 1

알고리즘

fillScreen(x, y, prevColor, newColor)

입력: (x,y) 시작 좌표, 이전 색상, 새 색상입니다.

출력 - 가능한 경우 이전 색상에서 새 색상으로 변경한 후의 화면입니다.

(x, y)가 화면 범위에 없으면 시작하고, (x, y) ≠ prevColor의 색상이면 반환하고, screen[x, y] 반환 :=newColor fillScreen(x+1, y, prevColor, newColor) fillScreen(x-1, y, prevColor, newColor) fillScreen(x, y+1, prevColor, newColor) fillScreen(x, y-1, prevColor, newColor)End

예시

#include#define M 8#define N 8using namespace std;int screen[M][N] ={ //화면 크기 및 색상 {1, 1, 1, 1, 1, 1, 1 , 1}, {1, 1, 1, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0, 1, 1}, {1, 2, 2, 2, 2 , 0, 1, 0}, {1, 1, 1, 2, 2, 0, 1, 0}, {1, 1, 1, 2, 2, 2, 2, 0}, {1, 1, 1 , 1, 1, 2, 1, 1}, {1, 1, 1, 1, 1, 2, 2, 1}};void fillScreen(int x, int y, int prevColor, int newColor) { //바꾸기 (x, y)의 이전 색상, 새 색상 if (x <0 || x>=M || y <0 || y>=N) //포인트가 화면을 초과할 때 리턴; if (screen[x][y] !=prevColor) // point(x,y)가 prevColor를 포함하지 않으면 아무 것도 하지 않습니다. return; 화면[x][y] =newColor; // 색상 업데이트 fillScreen(x+1, y, prevColor, newColor); //(x,y)의 오른쪽에 대해 fillScreen(x-1, y, prevColor, newColor); //(x,y)의 왼쪽에 대해 fillScreen(x, y+1, prevColor, newColor); //(x,y)의 상단에 대해 fillScreen(x, y-1, prevColor, newColor); //(x,y)의 바닥}void floodFill(int x, int y, int newColor) { int prevColor =screen[x][y]; //새 색상으로 바꾸기 전에 색상을 가져옵니다. fillScreen(x, y, prevColor, newColor);}int main() { int x =4, y =4, newColor =3; cout <<"이전 화면:"< 
출력
 <이전>이전 화면1 1 1 1 1 1 1 11 1 1 1 1 1 0 01 0 0 1 1 0 1 11 2 2 2 2 0 1 01 1 1 2 2 0 1 01 1 1 2 2 2 1 2 1 01 1 2 1 11 1 1 1 1 2 2 1업데이트된 화면:1 1 1 1 1 1 11 1 1 1 1 1 0 01 0 0 1 1 0 1 11 3 3 3 3 0 1 01 1 0 1 1 3 0 1 3 1 3 3 3 3 01 1 1 1 1 3 1 11 1 1 1 1 3 3 1