Rooms

시간 제한3.5초메모리 제한1024 MB

요약
알파벳 격자에서 같은 글자가 상하좌우로 연결된 방들을 구하고, 각 직사각형 질의에 겹치는 방의 개수를 센다.
난이도

어려움10점 중 8점

유형
그래프, DFS, 누적 합, 구현
정답자
아직 제출이 없습니다

문제

You are given a matrix with NN rows and MM 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 44 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 NN and MM.

Each of the following NN lines contains MM lowercase letters.

On the following line there is an integer QQ indicating the number of queries.

The next QQ lines contain 44 integers x_1x\_1, y_2y\_2, x_2x\_2, y_2y\_2, denoting a rectangle formed by the diagonally opposite points of coordinates (x_1,y_1)(x\_1,y\_1) and (x_2,y_2)(x\_2,y\_2).

출력

You should output QQ lines, each containing the answer for a query.

제한

  • 1≤N,M≤2,0001≤N,M≤2\\, 000
  • 1≤Q≤5,0001≤Q≤5\\, 000
  • 1≤x_1,x_2≤N1≤x\_1,x\_2≤N
  • 1≤y_1,y_2≤M1≤y\_1,y\_2≤M

예제1

  1. 예제 1

    입력
    5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6
    예상 출력
    12
8
6