熊猫烧香问题.doc

Project 3: Attack of Panda
Time Limit: 3 seconds
The computers in our network were connected in an array of M rows and N columns. Any one computer was connected directly to only the computers horizontally or vertically adjacent to it. At the beginning, T computers were infected with the Panda virus, each with a different variation, denoted by Type1, Type2, ... TypeT. Given that each computer in the network had a specific integer defense level L (0 < L < 1000). The Panda virus could rapidly spread across the network according to the following rules:
l The virus could only spread across the network from the infected computers to the clean ones;
l If a computer had already been infected by one variation of the virus, it would never be infected again by another variation;
l The attacking capability of the Panda virus would increase each day. In day 1, the virus could only infect computers with the defense level 1 provided that the virus could reach those computers. A computer with a defense level L > 1 could stop the virus. In day D, the virus could spread to all the computers connected with their defense level L £ D, provided that the virus was not stopped by any computer with a defense level L > D;
l Within the same day, the Type1 variation would attack first and infect all the computers it could reach. Then the virus variations Type2, Type3, ... TypeT would be activated in order.
Given the network in the following figure as an example:

In the 3´4 network, there were initially two computers infected by variations of Type1 and Type2, respectively. We may represent the status of the network by a 3´4 matrix, with –L representing a clean computer with defense level L, and a positive integer i representing the variation type index by which the computer was infected. Hence the given network corresponds to the matrix
.
In the first day, Type1 was stopped by its two neighboring computers, while Type2 attacked the two computers in the 3rd row with defense level 1. The matrix then becomes . In the second day, Type1 attacked all the clean computers with defense levels 1 and 2, while Type2 had nothing to do since the only clean computer it could reach had a defense level 3. The matrix now becomes . Finally in the third day, Type1 attacked all the rest of the clean computers and changed the matrix into .
Your task is to calculate the number of computers that were infected by some specific virus variations after all the computers were infected.
Input Specification:
Your program must read test cases from the standard input. The input will contain one or more test cases. Each test case begins with two integers M and N (1 £ M, N £ 500), followed by an M´N matrix which represents the initial status of the network. Then there is an integer Q indicating the number of queries. Each of the following Q lines gives a virus variation type.
The input ends with M and N both being 0. That case must NOT be processed.
Output Specification:
For each test case, output to the standard output. First print a line saying "Scenario #k", where k is the number of the test case (starting from 1). Then, for each virus variation, print the number of computers that were infected by it on a single line. Print a blank line between two test cases, but no extra line at the end of output.

Sample Input:
3 4
1 -3 -2 -3
-2 -1 -2 2
-3 -2 -1 -1
2
1
2
1 3
1 -1 2
2
1
2
0 0
Sample Output:
Scenario #1
9
3

Scenario #2
2
1

Hint:
Apply union-find to collect the computers infected by the same type of variation into the same set. Actually there is more than one way to solve this problem. Can you think of other solutions?

Grading Policy:
This assignment is due Sunday, October 30th, 2011 at 10:00pm.
l Programmer: Write the program (50 pts.) with sufficient comments.
l Tester: Provide a set of test cases to fill in a test report (20 pts.). Note that the tester is responsible, as well as the programmer is, for any bug later found by Judge. Write analysis and comments (10 pts.).
l Report Writer: Write Chapter 1 (6 pts.), Chapter 2 (12 pts.), and finally a complete report (2 pts. for overall style of documentation).