2017 자료구조

• Problem
• Standing
• Statistics
• Status
• Discuss

C - 영역 채우기

• Submit
• Status
• Discuss
• Summary

Description

컴퓨터 그래픽에서의 영역 채우기 알고리즘은 순환 기법을 사용한다. 영역 채우기란 다음과 같은 흰색 영역이 있을 때 이 영역을 특정한 색으로 채우는 것이다. 여기서는 이 영역 안쪽을 검정색으로 채운다고 가정해보라. 이런 경우에는 순환 호출을 어떻게 사 용할 수 있을까? 2차원 배열이 다음과 같이 되어 있다고 가정하고 영역안의 한점의 좌표가 주어졌을 경우에 안쪽을 채우는 순환 호출 함수를 작성하여 보라. ×로 표시된 픽셀이 시작 픽셀이다.

이문제를 해결하려면 먼저 왼쪽 그림을 2차원 배열을 이용하여 오른쪽 그림과 같이 나타낸다. 노란색은 2로, 흰색은 0으로 영역을 표시한 다음, 0의 값을 갖는 픽셀을 전부 1로 바꾸면 되는 것이다. 영역을 채운뒤의 결과를 출력해 보자

Input

* Line 1 : m n (행의개수m, 열의개수n, 0<m,n<30)

* Line 2 ~ m+1 : 공백으로 구분된 색깔. 단, 이미 검정색으로 채워진 픽셀은 존재하지 않는다. (0:White, 1:Black, 2:Yellow)

Output

* Line 1 ~ m : 공백으로 구분된 색깔 (0:White, 1:Black, 2:Yellow)

Sample Input

10 10
2 2 2 2 2 2 2 0 0 2
2 2 2 2 2 2 2 0 2 2
2 2 2 x 0 0 0 2 2 2
2 2 2 2 0 0 0 2 2 2
2 2 2 2 0 0 0 2 2 2
2 2 2 2 0 0 0 0 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2

Sample Output

2 2 2 2 2 2 2 0 0 2
2 2 2 2 2 2 2 0 2 2
2 2 2 1 1 1 1 2 2 2
2 2 2 2 1 1 1 2 2 2
2 2 2 2 1 1 1 2 2 2
2 2 2 2 1 1 1 1 2 2
2 2 2 2 1 2 2 2 2 2
2 2 2 2 1 2 2 2 2 2
2 2 2 2 1 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2

Hint

아래의 힌트 코드를 참고할 수 있습니다. (이 문제는 snippet judge가 아닙니다)

#define WHITE 0
#define BLACK 1
#define YELLOW 2

int screen[WIDTH][HEIGHT];
char read_pixel(int x, int y)
{
	return screen[x][y];
}
void write_pixel(int x, int y, int color)
{
	screen[x][y]=color;
}
void flood_fill(int x, int y)
{
	if (read_pixel (x, y) == WHITE)
	{
		write_pixel (x, y, BLACK);
		// 순환 호출
		// 순환 호출
		// 순환 호출
		// 순환 호출
	}
}

 

Source

c자료구조2장