표 분할
시간 제한3초메모리 제한256 MB
행 안쪽 두 곳과 열 안쪽 두 곳을 잘라 만든 3x3 분할에서 다섯 모서리 부분의 합이 짝수가 되는 자르기 쌍의 수를 센다.
문제
0과 1로 채워진 수 표 A[1..n, 1..m]를 생각하자. 1 ≤ r1 < r2 < n이고 1 ≤ c1 < c2 < m인 정수 네 개 (r1, r2, c1, c2)는 표를 그림과 같이 아홉 부분으로 나눈다.
A**i 부분에 있는 수의 합을 sum(A**i)라 하자. S = sum(A1) + sum(A3) + sum(A5) + sum(A7) + sum(A9)라 할 때, 주어진 표 A에 대해 S가 짝수인 분할의 개수를 구하라.
예를 들어 표
0101
0101
0100
에는 세 개의 분할이 있다. (r1=1, r2=2, c1=1, c2=2)와 (r1=1, r2=2, c1=1, c2=3)에서는 홀수 번호 부분에 있는 수의 합이 2, 즉 짝수이다. (r1=1, r2=2, c1=2, c2=3)에서는 합이 3, 즉 홀수이다. 따라서 조건을 만족하는 분할은 두 개이다.
입력
첫째 줄에 두 정수 n과 m이 주어진다. (3 ≤ n, m ≤ 3000) 다음 n개 줄에는 각각 m개 문자가 주어지며, 이는 표 A의 각 행이다.
출력
다음 조건을 모두 만족하는 네 정수 (r1, r2, c1, c2)의 개수를 출력하라.
- 1 ≤ r1 < r2 < n;
- 1 ≤ c1 < c2 < m;
- 표 A에서 홀수 번호 부분에 있는 수의 합이 짝수이다.