ZOJ Problem Set - 2849
In recent months, a computer virus spread across networks in China. The virus came with an icon of a lovely panda, hence the name Panda Virus. What makes this virus difficult to handle is that it has many variations.
Unfortunately, our lab's network was also infected with the Panda Virus. As you can see from the above diagram, the computers in our lab are placed in a matrix of M rows and N columns. A computer is only connected with the computers next to it. At the beginning, T computers were infected with the Panda Virus, each with a different variation (Type 1, Type 2... Type T). Each computer in the network has a specific defense level L (0 < L < 1000). The Panda Virus will rapidly spread across the network according to the following rules:
The following samples show the infection process described above:
At the beginning, only 2 computers were infected:
1 0 0 0
In day 1:
1 0 0 0
In day 2:
1 0 1 0
In day 3:
1 1 1 1
So at last, all the computers in the networks were infected by virus.
Your task is to calculate after all the computers are infected, how many computers are infected with some specific virus variations.
The input contains multiple test cases!
On the first line of each test case are two integers M and N (1 <= M, N <= 500), followed by a M * N matrix. A positive integer T in the matrix indicates that the corresponding computer had already been infected by the virus variations of type T at the beginning while a negative integer -L indicates that the computer has a defense level L. Then there is an integer Q indicating the number of queries. Each of the following Q lines has an integer which is the virus variation type we care.
For each query of the input, output an integer in a single line which indicates the number of computers attacked by this type of virus variation.
Author: XUE, Zaiyue
Source: Zhejiang Provincial Programming Contest 2007