Programming Assignment 4 Divine Ingenuity

CSC3100 Data Structures
Programming Assignment 4
Assignment Link: http://oj.cuhk.edu.cn/contest/csc310023falla4
Access Code: 9v7Dxqet
1 Divine Ingenuity (40% of this assignment)
1.1 Description
If you have ever played Genshin Impact, you must remember “Divine Ingenuity: Collector’s Chapter”
event. In this event, players can create custom domains by arranging components, including props
and traps, between the given starting point and exit point.
Paimon does not want to design a difficult domain; she pursues the ultimate “automatic map”. In
the given domain with a size of m × n, she only placed Airflow and Spikes. Specifically, Spikes will
eliminate the player (represented by ‘x’), while the Airflow will blow the player to the next position
according to the wind direction (up, left, down, right represented by ‘w’, ‘a’, ‘s’, ‘d’, respectively).
The starting point and exit point are denoted by ‘i’ and ‘j’, respectively. Ideally, in Paimon’s domain,
the player selects a direction and advances one position initially; afterward, the Airflow propels the
player to the endpoint without falling into the Spikes. The player will achieve automatic clearance in
such a domain.
However, Paimon, in her slight oversight, failed to create a domain that allows players to achieve
automatic clearance. Please assist Paimon by making the minimum adjustments to her design to
achieve automatic clearance.
Given that the positions of the starting point and exit point are fixed, you can only adjust components
at other locations. You have the option to remove existing component at any position; then, place a
new direction of Airflow, or position a Spikes.
1.2 Input
The first line of input contains two integers m and n, representing the size of the domain. m lines
follow, each containing n characters. The characters must be one of ‘w’, ‘a’, ‘s’, ‘d’, ‘x’, ‘i’ and ‘j’. It
is guaranteed that there is only one ‘i’ and ‘j’ on the map, and they are not adjacent.
1.3 Output
Output a single integer, representing the minimum number of changes needed.
Sample Input 1
3 3
dsi
ssd
jdd
Sample Output 1
1
4
You can make one modification to transform the domain as Fig. 2, allowing automatic clearance by
choosing to move left initially.
→ ↓ i
↓ ↓ →
j → →
Figure 1: Original Domain in Sample 1
→ ↓ i
↓ ↓ →
j ← →
Figure 2: Modified Domain in Sample 1
Sample Input 2
4 4
jxsx
xdxa
dxax
xwxi
Sample Output 2
4
You can make 4 modifications to transform the domain as Fig. 4, and choose to move upwards initially.
j x ↓ x
x → x ←
↓ x ← x
x ↑ x i
Figure 3: Original Domain in Sample 2
j ← ← x
x → ↑ ←
↓ x ← ↑
x ↑ x i
Figure 4: Modified Domain in Sample 2
You can find More Sample in the attached file on BB.
Problem Scale & Subtasks
Test Case No. Constraints
1-4 3 ≤ m, n ≤ 20
5-8 3 ≤ m, n ≤ 500
9-10 3 ≤ m, n ≤ 2000
Hint
Hint1 : The player cannot move outside the domain, and initially, they can choose any direction to
move from the starting point.
Hint2 : Consider the scenario where the cost is 0 when the player moves with the wind and 1 otherwise.
What can the original problem be transformed into?
2 Edge Changing (50% of this assignment)
2.1 Description
Give you a graph with n vertices and m edges. No two edges connect the same two vertices. For vertex
ID from 1 to n, we do the following operation: If any two neighbors of a vertex have a k× relationship
in terms of their IDs, we add a new edge between them. In other words, for any vertex i = 1 to n,
if u = kv or v = ku, we add an edge (u, v), where u, v ∈ Neighbor(i). Besides, if there is already an
edge between u and v, no operation is taken.
After the operation, we want you to output the BFS order starting from vertex s. Please traverse all
neighbors in ascending order of their IDs when expanding a vertex.
5
2.2 Input
The first line of input contains four integers n, m, k and s.
m lines follow, each containing two integers a, b, indicating that there is an edge between a and b.
There is no self-loop and repeated edges.
2.3 Output
Output the smallest BFS order of the new graph.
Sample Input 1
5 5 2 3
1 2
1 3
2 3
3 4
4 5
Sample Output 1
3 1 2 4 5
Figure 5: Original Graph Figure 6: Modified Graph
As shown in Fig. 6, due to the 2× relationship between neighbors 2 and 4 of vertex 3, We add a new
edge (2, 4) to the original graph.
You can find More Sample in the attached file on BB.
Problem Scale & Subtasks
For 100% of the test cases, 1 ≤ n, m ≤ 105
, 2 ≤ k ≤ 105
.
Test Case No. Constraints
1-4 n, m ≤ 100
5-7 n, m ≤ 1000
8-10 n, m ≤ 100000
Hint
For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It
may be too small for this problem. You need other data types, such as long long for C/C++ and long
for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the
input n. And the other operations for long and long long are quite same as int.
3 Obstacle (optional)
This question is optional and will not be included in the grade.
6
3.1 Description
In the piggy kingdom, there are n cities and m roads connecting them. A road connects two different
cities. For some reason, there are obstacles on some of the roads. The city 1 and city n are two
important cities of the kingdom, and many people travel between these two cities. However, because
of the obstacles, it may need more time to go from 1 to n. Now, the pig king wants to remove the
obstacles. Since it takes a lot of time and money to remove the obstacles, the king decides to only
remove two of them. Suppose the distance between city 1 and city n decreased by D after removing
the obstacles. The king wants to know the maximum value of D. Your task is to find this value.
3.2 Input
The first line of input contains two integers n and m.
m lines follow, each containing four integers a, b, c, d, indicating that there is a road between a and
b with length c. If d is 0, there is no obstacle on the road. If d is 1, there is an obstacle on the road.
There might be more than one road between two cities.
It is guaranteed that one can travel from city 1 to city n via the roads without obstacles.
3.3 Output
Output a single integer, representing the maximum value of D.
Sample Input 1
5 7
1 2 1 0
2 3 2 1
1 3 9 0
5 3 8 0
4 3 5 1
4 3 9 0
4 5 4 0
Sample Output 1
6
The original distance is 17, and the distance after removing the two obstacles is 11.
You can find More Sample in the attached file on BB.
Problem Scale & Subtasks
For 100% of the test cases, 1 ≤ n, m, c ≤ 105
.
7
Test Case No. Constraints
1-2 n, m ≤ 10
3-5 n, m ≤ 100
6-7 n, m ≤ 1000
8-10 n, m ≤ 100000
Hint
Hint1 : For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647.
It may be too small for this problem. You need other data types, such as long long for C/C++ and
long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input
n. And the other operations for long and long long are quite same as int.
Hint2 : Do not get stuck on the original graph. Try to build a new graph to solve the problem.
8