首页 > ACM题库 > HDU-杭电 > hdu 3059 Count Cross待解决[解题报告]C++
2014
03-01

hdu 3059 Count Cross待解决[解题报告]C++

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.