겹쳐 찍은 도장 자국
브론즈 II의견: 0
\(N\)행 \(M\)열의 흰 종이에 직사각형 도장 \(K\)개를 차례로 찍는다. \(i\)번째 도장은 왼쪽 위 칸 \((r_{1}, c_{1})\)부터 오른쪽 아래 칸 \((r_{2}, c_{2})\)까지의 직사각형 영역을 모두 검게 물들인다. 도장끼리 겹칠 수 있다.
\(K\)개의 도장을 모두 찍은 뒤, 검게 물든 칸(한 번이라도 도장이 닿은 칸)이 모두 몇 개인지 구하여라. 행과 열은 각각 \(1\)부터 \(N\), \(1\)부터 \(M\)까지이다.
\(1 \le N, M \le 500\), \(1 \le K \le 20\), \(1 \le r_1 \le r_2 \le N\), \(1 \le c_1 \le c_2 \le M\)
첫째 줄에 \(N\), \(M\), 도장의 개수 \(K\)가 주어진다.
다음 \(K\)개의 줄에 각각 도장의 왼쪽 위와 오른쪽 아래 좌표 \(r_1\), \(c_1\), \(r_2\), \(c_2\)가 주어진다. \(r_1 \le r_2\), \(c_1 \le c_2\)이다.
검게 물든 칸의 개수를 출력한다.
4 4 2
1 1 2 2
2 2 3 3
7
두 도장은 \((2,2)\) 한 칸에서 겹친다. 각각 \(4\)칸이므로 합집합은 \(4+4-1 = 7\)칸이다.
3 3 1
1 1 3 3
9
도장 하나가 판 전체를 덮으므로 자국은 \(9\)칸이다.
riseoj 작성
출처 Original
평가 및 의견
겹쳐 찍은 도장 자국
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
겹쳐 찍은 도장 자국