가장 큰 빈 별 부분격자 질의
플래티넘 V의견: 0
\(R \times C\) 크기의 정적인 격자가 주어진다. 각 칸은 별 * 또는 점 . 둘 중 하나이다. 이 격자는 절대 변하지 않는다.
이제 \(Q\) 개의 직사각형 질의가 들어온다. 각 질의는 격자 위의 한 직사각형 창 \((r_1, c_1, r_2, c_2)\) 로 주어지며, 행 \(r_1 \dots r_2\) 와 열 \(c_1 \dots c_2\) 로 둘러싸인 부분격자를 가리킨다.
각 질의에 대해, 그 창 안에 완전히 포함되면서 모든 칸이 별인 축에 평행한 직사각형 중 넓이(칸 수)가 가장 큰 것의 넓이를 출력하라. 창 안에 별 칸이 하나도 없다면 답은 \(0\) 이다.
참고: 같은 격자에 대해 질의가 매우 많이 들어올 수 있으므로, 매 질의마다 처음부터 다시 계산하는 것보다 훨씬 빠른 방법이 필요하다. 단조 스택을 이용한 히스토그램 최대 직사각형 기법을 오프라인 처리·2차원 구간 자료구조와 결합하는 접근이 대표적이다.
\(1 \le R, C\) 이고 \(R \cdot C \le 2{,}500\)
\(1 \le Q \le 100{,}000\)
\(1 \le r_1 \le r_2 \le R\), \(1 \le c_1 \le c_2 \le C\)
첫째 줄에 세 정수 \(R\), \(C\), \(Q\) 가 주어진다.
다음 \(R\) 개의 줄에는 각각 길이 \(C\) 인 문자열이 주어지며, 격자의 한 행을 나타낸다. 각 문자는 * (별) 또는 . (점) 이다.
다음 \(Q\) 개의 줄에는 각각 네 정수 \(r_1\ c_1\ r_2\ c_2\) (\(1 \le r_1 \le r_2 \le R\), \(1 \le c_1 \le c_2 \le C\)) 가 주어진다. 행과 열은 모두 \(1\) 부터 시작한다.
각 질의에 대해 한 줄씩, 그 창 안에 완전히 들어가는 모든-별 직사각형 중 최대 넓이를 출력한다.
4 5 3
*.***
*****
**.**
*****
1 1 4 5
1 3 4 5
3 1 4 2
8
8
4
격자(1-인덱스)에서 (1,2)와 (3,3)에만 점이 있다.
질의 1 (전체판): 마지막 두 열(4,5열)은 네 행 모두 별이므로 4×2 = 8 이 최대이다.
질의 2 (3..5열): 3열에는 (3,3) 점이 있지만 4,5열은 네 행 모두 별이라 4×2 = 8.
질의 3 (3..4행 × 1..2열): 네 칸 모두 별 → 2×2 = 4.
3 3 2
***
*.*
***
1 1 3 3
1 1 2 2
3
2
가운데 (1,1)이 점이다.
질의 1: 점 때문에 2×2는 불가능, 1×3 한 줄이 최대 → 3.
질의 2: (0,0),(0,1),(1,0)은 별, (1,1)은 점 → 최대 1×2 = 2.
riseoj 작성
출처 Original
평가 및 의견
가장 큰 빈 별 부분격자 질의
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
가장 큰 빈 별 부분격자 질의