CS 602
Algorithm Design and Implementation

Assignment 4

[Question 1] Flooded Zones – Part 1
The Temapura city government has placed many sensors for the coming rain season, to detect
flooded zones. From the sensor data, they wish to understand how large a flooded zone can be, so
to arrange evacuation plans accordingly.
Suppose the city is divided into a grid of blocks of n rows and m columns, and there is one sensor
for each block. Each sensor will send a signal to the control station, if the corresponding block is
flooded, the symbol “#” appears on the screen at the control station, otherwise, the symbol “.”
appears on the screen. All symbols form a rectangular matrix of n rows and m columns, with one
symbol corresponds to one block at its relative position. When there are two “#” symbols next to
each other in the same row or in the same column appearing on the screen, the two blocks are both
flooded and joined as one single flooded zone. Assume the area of each block is the same, the area
of a flooded zone can be calculated by the number of “#” symbols joined together.
Implement an algorithm in the function largest_flooded_zone_1 to calculate the area of the
largest flooded zone given a rectangle of symbols.
Test inputs starts from the number of test cases. For each test case, the first line contains a pair of
integers n (1 ≤ n ≤ 200) and m (1 ≤ m ≤ 200), followed by n lines of m symbols, where each line
is a combination of symbol “#” and symbol ‘.’, representing if the corresponding block is flooded.
For each test case, output one integer representing the number of blocks in the largest flooded
zone.
Sample Input
3
3 4
####
.#.#
###.
3 3
#.#
.#.
#.#
3 5
#####
#..##
#####
Sample Output
9
1
13


[Question 2] Flooded Zones – Part 2
Let us now assume a block surrounded by one single flooded zone is also considered as a part of
the flooded zone since it is inaccessible. We say a block is surrounded by one single flooded zone
if there is no access from the boundaries (of the entire map) to this block without entering the
flooded zone by moving left, right, up or down. If this block can be accessed from another flooded
zone (accessible via flooded zones, but such flood zone is not unique), it is not considered as
surrounded by this flooded zone.
Implement an algorithm in the function largest_flooded_zone_2 to calculate the area of the
largest flooded zone with the new definition above.
Test inputs starts from the number of test cases. For each test case, the first line contains a pair of
integers n (1 ≤ n ≤ 200) and m (1 ≤ m ≤ 200), followed by n lines of m symbols, where each line
is a combination of symbol “#” and symbol ‘.’, representing if the corresponding block is flooded.
For each test case, output one integer representing the number of blocks in the largest flooded
zone.
Sample Input
3
3 4
####
.#.#
###.
3 3
#.#
.#.
#.#
3 5
#####
#..##
#####
Sample Output
10
1
15





Grading Rubrics:
1. There are 10 marks for each question.
2. There are 10 test cases for question 1 and 2, where the first test case is the sample input
A4Q1.in and A4Q2.in respectively. You get 1 mark for each test case if your code does not
produce errors including wrong answer or time limit exceeded.


Running python skeleton with sample input:
1. Open “Anaconda Prompt”
2. Go to the directory where you put the file A4Q1.py and A4Q1.in, using command cd
3. Run command python A4Q1.py < A4Q1.in
4. You may want to create a test input called my_own_test.in to design a test case for your
own program, the command would then be python A4Q1.py < my_own_test.in
5. Same applies to Question 2, so you may run python A4Q2.py < A4Q2.in
6. Make sure your program read input from sys.stdin. If you find it difficult to work with
sys.stdin, you might write the function that your need to modify with your own input
and output, and then copy and paste to the function itself to the code skeleton provided.
Please test with the command in item 3 to ensure it produces the right output.



































































































学霸联盟