COMP2119 Introduction to data structures and algorithms Assignment 3
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP2119 Introduction to data structures and algorithms
Assignment 3 (Programming)
Part 1 (Graph)
(Only Part 1 is mandatory and graded.)
Q 1. Consider a “matrix map” of cells arranged as an m ⇥ n matrix. Each cell in the map is referred to by a “location” . Specifically, the location of the upper left corner cell of the map is (0,0), and the location of the lower right corner cell of the map is (m − 1,n − 1). Each cell in the map has one of two values 0 and 1. A cell with value 0 means that it is an empty cell where a robot is allowed to move into. A cell with value 1 means that it is a wall where a robot can not move into. A robot is to navigate through the map starting at location (0, 0) until it reaches location (m − 1,n − 1). Robot movements are restricted by two rules: (1) The robot can move only within the map. (2) The robot can move up, down, left or right by one step each time to a neighbouring cell. Also, we cells (0, 0) and (m − 1,n − 1) are empty. Write programs to solve the following problems:
(a) [40%] Write a program that, given a matrix map, returns the least number of steps that the robot need to take to travel from cell (0, 0) to cell (m − 1,n − 1). Your program should return “−1” if there are no valid routes. Here are some examples:
• Example 1:
|
0 |
Input: grid=[[0]]
Output: 0
•
•
Example 2:
|
0 |
1 |
|
1 |
0 |
Input: grid=[[0, 1], [1, 0]]
Output: -1
Example 3:
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
0 |
0 |
0 |
Input: grid=[[0, 0, 1], [0, 1, 0], [0, 0, 0]]
Output: 4
cell (m − 1,n − 1). Some examples:
• Example 1:
|
0 |
Input: grid=[[0]]
Output: 1
• Example 2:
|
0 |
1 |
|
1 |
0 |
Input: grid=[[0, 1], [1, 0]]
Output: 2
• Example 3:
|
0 |
0 |
1 |
|
1 |
1 |
1 |
|
1 |
0 |
0 |
Input: grid=[[0, 0, 1], [1, 1, 1], [1, 0, 0]]
Output: 4
(c) [30%] Now, assume that the robot can eliminate k walls, where k ≥ 1. Repeat part (b). Some examples:
• Example 1:
0
Input: grid=[[0]], k = 1
Output: 0
•
•
Example 2:
|
0 |
1 |
|
1 |
0 |
Input: grid=[[0, 1], [1, 0]], k = 1
Output: 2
Example 3:
|
0 |
1 |
1 |
|
1 |
1 |
1 |
|
1 |
1 |
0 |
Input: grid=[[0, 1, 1], [1, 1, 0], [1, 1, 0]], k = 2
Output: -1
Note:
1. You should complete the assignment in Python 3. You are allowed to use ‘collections’ package, ‘heapq’ package, ‘set’ and ‘list’ directly in your programs.
2. You should complete certain files provided in the A3 folder (see below). You can only modify the functions leastStepQ1a, leastStepQ1b, leastStepQ1c and theLeastPrice.
A3
A3 P1 1a .py The leastStepQ1a function in this file is for Q1(a) in part 1
3. Some test cases are provided but you are encouraged to design your own test cases. The autograding result will be shown on your terminal once you run ‘python A3 P1 1a.py’, ‘python A3 P1 1b.py’, ‘python A3 P1 1c.py’ . Your score in the assignment will be evaluated by other (unrevealed) test cases, which are not used by the autograder. You should organize your submitted files in the following way. Please replace the UID by your university number and make sure your programs can run normally before you zip the folder UID as a UID.zip file.
UID
A3 P1 1a .py This is your code file for Q1(b)in part 1
understand your algorithms of Q1 in part 1
4. In the leastStepQ1a function and leastStepQ1b function, there will be one parameter, grid . In the canReachQ1c function, there will be two parameters, grid and k . The structure of the parameter grid is List[List[int]]. The data type of k is int. The output variable of these three functions are int.
2022-04-06