32938번 - Counting portal

마인크래프트는 다양한 종류의 블록을 이용해 구조물을 만들 수 있는 게임이다. 게임 내에서 블록은 다음 3가지 종류로 구분할 수 있다.

• 빈 공간(0): 비어 있는 공간으로, 어떤 블록도 없는 상태이다.
• 옵시디언 블록(1): 특수한 블록으로, 문제에서 중요한 역할을 하는 블록이다.
• 그 외의 블록(2): 나무 블록, 흙 블록 등이 해당된다.

마인크래프트에는 지옥문이라는 특별한 구조물이 있다. 지옥문은 특정한 조건을 만족하는 직사각형 모양의 구멍의 형태를 갖춘 구조물로, 지옥으로 이동하는 통로로 사용된다.

높이 $N$, 너비 $M$인 직사각형 모양의 현재 상태 $S$가 주어진다. 위치 ($r, c$)에 해당되는 $S_{r, c}$는 현재 상태 $S$의 $r$번째 행, $c$번째 열에 해당되는 블록을 나타내며, 위에서 언급한 3가지 종류의 블록(0, 1, 또는 2) 중 하나이다.

두 위치 ($r_1, c_1$), ($r_2, c_2$)를 각각 직사각형의 왼쪽 위 꼭짓점과 오른쪽 아래 꼭짓점으로 하여 지옥문을 만들고자 한다. 플레이어는 블록을 제거할 수 없고, 옵시디언 블록만을 자유롭게 설치할 수 있는 상황이다. 이 경우, 지옥문을 만들 수 있는 조건은 다음과 같다.

• $r_2 - r_1 \ge 4, c_2 - c_1 \ge 3$
• $c_1 \lt c \lt c_2$를 만족하는 모든 $c$에 대해, $S_{r_{1},c} \neq 2$이고 $S_{r_{2},c} \neq 2$이다.
• $r_1 \lt r \lt r_2$를 만족하는 모든 $r$에 대해, $S_{r,c_{1}} \neq 2$이고 $S_{r,c_{2}} \neq 2$이다.
• $r_1 \lt r \lt r_2, \ c_1 \lt c \lt c_2$를 만족하는 모든 순서쌍 ($r, c$)에 대해, $S_{r,c}=0$이다.

실제 마인크래프트와는 달리, 여기서 지옥문의 최대 크기에는 제한이 없다.

이 때, 지옥문을 만들 수 있는 순서쌍 ($r_1, c_1, r_2, c_2$)의 개수를 구하여라.

첫 번째 줄에 현재 상태 $S$의 크기 $N$과 $M$이 주어진다. ($5 \le N \le 300$, $4 \le M \le 300$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $M$개의 수가 공백으로 구분되어 주어진다. $i+1$번째 줄의 $j$번째 수는 $S_{i,j}$를 나타낸다. 0은 비어있는 상태, 1은 옵시디언 블록으로 채워진 상태, 2는 그 외의 블록으로 채워진 상태이다.

조건에 따라 지옥문을 만들 수 있는 순서쌍 ($r_1, c_1, r_2, c_2$)의 개수를 출력한다.

예제 1에서, 조건에 따라 지옥문을 만들 수 있는 순서쌍의 개수는 3개이다.