首页 > 代码库 > poj 3112 Digital Biochemist Circuit(简单题)

poj 3112 Digital Biochemist Circuit(简单题)

题目链接:http://poj.org/problem?id=3112

Digital Biochemist Circuit
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 876 Accepted: 375

Description

A digital biochemist circuit (DBC) is a device composed of a set of processing nodes. Each processing node consists of a small receptacle for holding biochemist agents. The receptacle is made of a biological substance that works like a digital circuit. Depending on the states of reactions in the receptacle, the substance may generate two levels of voltage. A reader connected to a DBC is capable of reading all processing nodes of the DBC instantaneously, interpreting the two levels of voltage as 0 or 1.

An experiment with the DBC is carried out in the following way. The processing nodes are loaded with the substances of interest and appropriate reagents and, for every fixed time interval (typically several milliseconds), the voltage of processing nodes are read. Thus, the experiment results in a sequence of bit sets (vectors), each corresponding to a measurement of the DBC.

A sequence of 1-bits uninterrupted throughout the time of a processing node is called a run. The length of a run is the number of 1-bits in the sequence (note that the length of runs of an experiment can vary between one and the number of measurements made). One important characteristic of an experiment with the DBC is the number and length of the runs generated. The figure below shows the result of an experiment carried out with a DBC of six processing nodes, on which four measurements are made, containing three runs of length one, one run of length two and one run of length four.

0 1 0 1 1 0
0 0 0 1 0 0
0 1 0 1 0 1
0 1 0 1 0 0

You are contracted to write a program that determines, given the result of an experiment, how many runs of length that is equal to or greater than a certain value are generated.

Input

The input contains several test cases. The first line of test case contains three integers PN and C which indicate the number of processing nodes (1 ≤ P ≤ 1000), the number of measurements made (1 ≤ N ≤ 1000) and the minimum length of runs of interest (1 ≤ C ≤ N), respectively. Each of the next N lines contains P digits {0, 1} separated by a whitespace. The end of the input is indicated by P = N = C = 0.

Output

For each test case in the input your program should produce a single line of output, containing the number of runs of length greater than or equal to C produced by the experiment.

Sample Input

2 2 2
1 1
1 1
4 5 3
0 1 0 1
1 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
0 0 0

Sample Output

2
2

Source

South America 2006, Brazil Subregion

题目大意:统计每一列中连续为1的段大于等于p的数量;

具体见代码解析!

代码如下:

#include <cstdio>
#include <cstring>
int main()
{
	int n, m, p;
	int ans;
	int a[1017];
	int i, j;
    while (scanf("%d%d%d",&m, &n, &p))
    {
		memset(a, 0, sizeof(a));//初始化
		if(n == 0 && m == 0 && p == 0)
			break;
		ans = 0;
		int x;
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				scanf("%d",&x);
				if(x)
					a[j]++; //统计同一列连续的个数
				else if(a[j] != 0)//间断
				{
					if(a[j] >= p)//计数
						ans++;
					a[j] = 0;//间断,重新开始计数
				}
			}
		}
		for(i = 0; i < m; i++)//最后还要做一次统计,因为有可能到最后也没有间断;
		{						//那么上面就没有统计到这种情况
			if (a[i] >= p)
				ans++;
		}
		printf("%d\n", ans);
    }
    return 0;
}