Informatica Online Judge

  구간 컴포넌트 수 [1840 / 0730]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs17018 - 157ms / 1086byte
My Best Submission (C++) : N/A

[AtCoder Grand Contest 015 C]

Background

경곽이는 n*m지도를 받았다.

이 행렬의 각 원소는 0 또는 1이다.

0은 값이 없는 것이고, 1은 값이 있는 것이다.

이 지도의 임의의 1로부터 다른 1로의 경로는 한 번 거친 칸을 다시 방문하지 않고 간다고 할 때, 많아야 1개뿐이다.

경곽이는 이 지도의 일부 (x1, y1) ~ (x2, y2)로 이루어진 직사각형 영역 내에서 상, 하, 좌, 우로 연결된 1의 덩이리(컴포넌트)의 수를 세고자 한다.

q개의 질문이 주어진다. 이 질문은 x1, y1, x2, y2의 형태이다.

각 질문들에 대해서 해당 영역에 컴포넌트가 몇 개씩 존재하는지 출력하는 프로그램을 작성하시오.

Input

첫 번째 줄에 영역의 행과 열의 크기를 나타내는 자연수 n, m과 질문의 수 q가 공백으로 구분되어 입력된다.

두 번째 줄부터 n줄에 걸쳐서 m개의 0또는 1로 이루어진 문자열이 입력된다.

다음 줄부터 q줄에 걸쳐서 각 줄에 x1, y1, x2, y2의 값이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n, m <= 2,000
1 <= q <= 200,000
1 <= x1 <= x2 <= n
1 <= y1 <= y2 <= m

Output

각 질문에 대해서 영역의 개수를 한 줄에 하나씩 출력한다.

IO Example

입력
3 4 4
1101
0110
1101
1 1 3 4
1 1 3 1
2 2 3 4
1 2 2 4

출력
3
2
2
2

* 설명 : 다음 그림을 참고하여 파란색의 수를 카운팅하면 된다.
빨간 사각형은 두 번째 질문에 대한 영역이고 이 때 파란색은 위, 아래의 2개의 컴포넌트로 구성된다.



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]