31843번 - Rooms 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3.5 초 | 1024 MB | 69 | 25 | 13 | 38.235% |
문제
You are given a matrix with $N$ rows and $M$ columns which contains lowercase letters of the English alphabet.
A room is a maximal component of cells which share the same letter and which are connected in $4$ directions: up, down, left, right.
You have to answer queries of the type: "How many rooms are completely or partly included in a given rectangular submatrix?".
입력
The first line contains two integers $N$ and $M$.
Each of the following $N$ lines contains $M$ lowercase letters.
On the following line there is an integer $Q$ indicating the number of queries.
The next $Q$ lines contain $4$ integers $x_1$, $y_2$, $x_2$, $y_2$, denoting a rectangle formed by the diagonally opposite points of coordinates $(x_1,y_1)$ and $(x_2,y_2)$.
출력
You should output $Q$ lines, each containing the answer for a query.
제한
- $1≤N,M≤2\, 000$
- $1≤Q≤5\, 000$
- $1≤x_1,x_2≤N$
- $1≤y_1,y_2≤M$
예제 입력 1
5 6 aabbcc abbbcc cbeaed adeeed affttz 3 1 1 5 6 2 1 4 5 3 3 5 6
예제 출력 1
12 8 6
There are $3$ queries.
The 1 1 5 6 query refers to the whole matrix, which has $12$ rooms.
The 2 1 4 5 rectangle contains $8$ rooms, $4$ of which are complete.
The 3 3 5 6 rectangle contains $6$ rooms, $5$ of which are complete.