문제 1014 · 기초 3
회의실 빈자리 지도
누적합 · 2차원 배열
테스트별 제한 2000ms · 브라우저 채점
문제
큰 강당의 좌석 배치가 R행 C열 격자로 주어진다. '#' 은 이미 누가 맡은 자리, '.' 은 빈자리다. 팀 단위로 자리를 잡으려는 사람들이 직사각형 영역을 하나씩 묻는다. 각 질문마다 그 영역 안의 빈자리 수를 답하라. 영역은 왼쪽 위 칸 (r1, c1) 과 오른쪽 아래 칸 (r2, c2) 으로 주어지며 두 칸을 포함한다. 행과 열 번호는 1부터 센다.
입력
첫째 줄에 R 과 C 가 주어진다. (1 ≤ R, C ≤ 300) 다음 R개 줄에 길이 C 인 문자열이 주어진다. 문자열은 '#' 과 '.' 로만 이루어져 있다. 그다음 줄에 질문 수 Q (1 ≤ Q ≤ 10,000) 가 주어지고, 다음 Q개 줄에 r1 c1 r2 c2 가 주어진다. (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C)
출력
질문마다 한 줄에 빈자리 수를 출력한다.
예제 입력 1
3 4 #..# .... ##.# 3 1 1 3 4 2 2 3 3 1 1 1 1
예제 출력 1
7 3 0
힌트 펼치기
- S[i][j] 를 (1,1) 부터 (i,j) 까지의 빈자리 수로 미리 구해 두면 질문 하나를 덧셈·뺄셈 네 번으로 답할 수 있다.
- 영역의 답 = S[r2][c2] − S[r1−1][c2] − S[r2][c1−1] + S[r1−1][c1−1].
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.