xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CS 602 -Assignment 4

时间：2021-03-25

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.

学霸联盟

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.

学霸联盟