횡단막 (Banner)

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

요약

H x W 격자에서 네 꼭짓점이 모두 기둥인 직사각형 중, 꼭짓점 색에 검정, 회색, 흰색이 모두 포함된 직사각형의 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 조합론, 행렬
정답자: 아직 제출이 없습니다

횡단막 (Banner)

20XX년, 드디어 IOI가 JOI 국에서 개최되게 되었다. JOI 국에서는 이를 축하하기 위해 도시 곳곳에 환영 횡단막을 걸기로 했다. 그림처럼 동서 방향으로 난 도로 H개와 남북 방향으로 난 도로 W개가 바둑판 모양으로 교차한다. 동서 도로와 남북 도로가 만나는 지점을 교차점이라 한다. 북쪽에서 a번째, 서쪽에서 b번째 교차점은 $(a, b)$ 로 나타낸다.

각 교차점에는 기둥이 하나씩 서 있다. JOI 국을 상징하는 색은 검은색, 회색, 흰색 세 가지이며, 각 기둥은 이 중 한 가지 색으로 칠해져 있다.

그림: JOI 국의 지도 (H = 3, W = 4인 경우). 그림의 위쪽이 북, 왼쪽이 서에 해당한다.

횡단막은 이 기둥들을 받침대로 삼아 걸 수 있다. 다만 횡단막이 도로가 아닌 곳을 지나면 방해가 된다. 그래서 교차점에 서 있는 기둥 중에서 각 변이 어느 도로와 평행한 직사각형의 네 꼭짓점에 있는 서로 다른 기둥 네 개를 골라, 그 둘레에 횡단막을 건다. 이때 고른 기둥 네 개에는 검은색, 회색, 흰색 기둥이 각각 하나 이상 포함되어야 한다.

이러한 방식으로 기둥 네 개를 고르는 방법은 몇 가지인가?

입력

표준 입력에서 다음 입력을 읽어라.

첫 줄에는 정수 H, W가 공백으로 구분되어 주어진다.

이어지는 H개의 줄에는 교차점에 서 있는 기둥의 색 정보가 주어진다. i + 1번째 줄 (1 ≤ i ≤ H)에는 0, 1, 2 중 하나인 정수 W개가 공백으로 구분되어 적혀 있다. i + 1번째 줄의 j번째 정수가 0이면 교차점 (i, j)의 기둥은 검은색, 1이면 회색, 2이면 흰색이다.

출력

표준 출력에 기둥 네 개를 고르는 방법의 수를 한 줄로 출력하라.

제한

2 ≤ H ≤ 400: 동서 방향으로 난 도로의 개수
2 ≤ W ≤ 400: 남북 방향으로 난 도로의 개수

힌트

이 입력 예시에서 기둥 네 개를 고르는 방법은 다음 12가지가 있으므로 12를 출력한다.

(1, 1), (2, 1), (2, 2), (1, 2)
(1, 1), (2, 1), (2, 4), (1, 4)
(1, 2), (2, 2), (2, 3), (1, 3)
(1, 3), (2, 3), (2, 4), (1, 4)
(1, 1), (3, 1), (3, 4), (1, 4)
(1, 2), (3, 2), (3, 3), (1, 3)
(1, 2), (3, 2), (3, 4), (1, 4)
(1, 3), (3, 3), (3, 4), (1, 4)
(2, 1), (3, 1), (3, 2), (2, 2)
(2, 1), (3, 1), (3, 3), (2, 3)
(2, 2), (3, 2), (3, 4), (2, 4)
(2, 3), (3, 3), (3, 4), (2, 4)

예제1

예제 1
입력
```
3 4
0 1 0 2
1 2 0 1
0 0 2 1
```
예상 출력
```
12
```