2014
03-01

# Count Cross

Given a MM×NN grid with different colors(black and white) on each cell, your task is to calculate the total amount of crosses of black color. We say there exists a black cross centered at the black cell (x,y) if there are four positive integer L,R,U,D that the cell(x,y-L),(x,y+R),(x-U,y),(x+D,y) are all black. Note that if two crosses have the same center but different L,R,U,D, we consider they are distinct.We use 1 to describe black.

For example

00100
00100
11111
00100
00100
00000

There are 16 black crosses.

The MM and NN are large, so we divide the matrix into M×N rectangle blocks.If two cells are in the same block ,their colors are same.

So we can divide the sample into 4×3 blocks.

There are at most 100 cases.

In every case,there are two integers, M, N in the first line. (1≤M, N≤50)

The next line contains M positive integers which are less than or equals to 50. The p-th integer describe the p-th row block’s height.

The next line contains N positive integers which are less than or equals to 50. The p-th integer describe the p-th colomn block’s width.

The following M lines each has a string which contain N digits.The q-th digit in the p-th line describe the color of the q-th colomn block in the p-th row.

There are at most 100 cases.

In every case,there are two integers, M, N in the first line. (1≤M, N≤50)

The next line contains M positive integers which are less than or equals to 50. The p-th integer describe the p-th row block’s height.

The next line contains N positive integers which are less than or equals to 50. The p-th integer describe the p-th colomn block’s width.

The following M lines each has a string which contain N digits.The q-th digit in the p-th line describe the color of the q-th colomn block in the p-th row.

4 3
2 1 2 1
2 1 2
010
111
010
000 

16

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.