백준 2583. 영역 구하기

tose33 2022. 3. 29. 15:53

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

직사각형의 두 좌표가 (x1,y1), (x2,y2)라면 해당 직사각형이 차지하는 공간은 (x1,y1) 부터 (x2-1, y2-1) 까지 이다.

예를들어 좌표가 (0,2), (4,4)라면 해당 직사각형이 차지하는 공간은

(0,2) (1,2), (2,2) (3,2)

(0,3) (1,3), (2,3) (3,3)

이렇게 모든 직사각형들이 차지하는 공간을 채워주고 bfs 알고리즘으로 비어 있는 공간을 탐색하면서 채워나가면 된다.