问题 6176. -- NOI2012湖北省选 一试 第1题 双十字

6176: NOI2012湖北省选 一试 第1题 双十字

时间限制: 10 Sec  内存限制: 512 MB
献花: 0  解决: 0
[献花][花圈]

题目描述

在C 部落,双十字是非常重要的一个部落标志。所谓双十字,如下面两个例子,由两条水

平的和一条竖直的“1”线段组成,要求满足以下几个限制:

. 两条水平的线段不能在相邻的两行。
. 竖直线段上端必须严格高于两条水平线段,下端必须严格低于两条水平线段。
. 竖直线段必须将两条水平线段严格划分成相等的两半。
. 上方的水平线段必须严格短于下方的水平线段。
所以上面右边的例子是满足要求的最小的双十字。
现在给定一个R×C 的01 矩阵,要求计算出这个01 矩阵中有多少个双十字。

例如下面这个例子,R=6,C=8,01 矩阵如下:


输入

第一行为用空格隔开的两个正整数R和C,分别表示
01矩阵的行数和列数。输入文件第二行是一个非负整数N,表示01矩阵中“0”的个数。接下来的
N行,每行为用空格隔开的两个正整数x和y(1≤x≤R,1≤y≤C),表示(x,y)是一个“0”。数据
保证N个“0”的坐标两两不同。数据保证R,C,N≤10,000,R*C≤1,000,000.对于30%的数据
R,C≤50.

输出

仅包含一行,为D mod 1,000,000,009 的结果,其中D 为要求的01
矩阵中双十字的个数。

样例输入

6 8
12
1 2
1 3
1 4
1 6
2 2
3 2
3 3
3 4
3 7
6 4
6 6
4 8

样例输出

5

提示

来源

[献花][花圈]