Question 7

5

1 votes
Very-Easy
Problem

Solve (5) with the constraint that the agent can convert a maximum of γ obstacles into non-obstacles and pass them. Here γ is an additional input. Order is m, n, η, γ and α.

Sample Input
3
14 13 9 1 2
0 0 0 0 0 0 0 0 0 0 0 0 0 
-1 -1 -1 0 0 0 0 -1 -1 0 -1 -1 0 
-1 -1 -1 -1 0 0 0 -1 -1 0 -1 -1 0 
-1 -1 -1 -1 0 0 0 0 0 0 -1 -1 0 
0 0 0 0 0 0 0 2 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 -1 -1 -1 0 3 
0 0 0 0 0 0 0 0 -1 -1 -1 0 0 
0 0 0 0 0 0 0 0 -1 -1 -1 0 0 
0 0 0 0 0 0 0 0 -1 -1 0 0 0 
-1 -1 0 0 0 0 0 4 -1 -1 -1 -1 0 
-1 -1 -1 -1 -1 0 0 4 0 0 -1 -1 0 
0 0 -1 -1 -1 0 1 0 0 0 -1 -1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 
2 12
14 12 11 1 2
0 -1 -1 0 0 0 0 0 0 0 0 0 
0 -1 -1 0 0 0 0 0 0 0 0 0 
0 -1 -1 0 0 0 0 3 0 0 0 0 
0 0 2 0 -1 -1 -1 -1 0 0 0 0 
0 -1 -1 0 -1 -1 -1 -1 0 0 0 0 
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 
0 0 -1 -1 -1 0 0 -1 -1 -1 1 0 
0 0 -1 -1 -1 0 0 0 0 0 2 0 
0 0 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 -1 -1 -1 0 0 0 4 0 
0 0 -1 -1 -1 -1 -1 0 0 0 0 0 
0 0 -1 -1 0 0 0 0 0 0 0 0 
0 0 -1 -1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 2 0 0 
1 6
12 11 8 1 2
0 -1 -1 -1 0 -1 -1 0 0 0 0 
-1 -1 -1 -1 0 -1 -1 0 0 0 0 
0 -1 -1 -1 -1 0 0 0 0 -1 0 
0 0 0 0 -1 0 0 0 0 0 0 
0 -1 -1 -1 -1 0 0 -1 -1 0 0 
0 -1 -1 -1 -1 0 0 -1 -1 0 0 
0 0 0 0 0 0 0 4 3 0 0 
0 0 0 0 -1 -1 0 3 0 0 0 
0 0 0 0 -1 -1 0 0 0 -1 0 
0 0 0 0 0 0 3 0 0 -1 0 
0 0 2 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 
6 6
Sample Output
2 12 3 12 4 12 5 12 6 12 7 12 8 11 9 10 10 9 11 8 11 7 10 7 
1 6 2 7 3 8 4 9 5 10 6 11 7 10 8 10 9 10 10 10 11 10 12 10 13 9 
6 6 6 7 6 8 7 7
Time Limit: 10
Memory Limit: 256
Source Limit:
Editor Image

?