Question 5
Problem
Solve (1) with the difference that there are multiple gems. Each gem has points as written on the grid map. The aim is to collect a total of at least η points. The gem is automatically picked up on moving to the cell containing it, however an extra cost of α is incurred. η and α are additional inputs supplied along with m and n. Order is m, n, η and α. 1≤ m, n ≤20, 1 ≤ maximum number of gems ≤ 20
5 14 12 11 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 4 14 13 9 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 11 14 9 2 0 -1 -1 0 4 0 0 0 0 0 0 0 0 0 0 -1 -1 0 -1 -1 -1 0 3 0 0 1 0 0 0 0 -1 0 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 -1 0 0 0 -1 0 -1 -1 0 0 0 -1 -1 0 -1 2 0 0 -1 0 -1 -1 0 0 0 -1 0 -1 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 0 0 0 0 0 1 0 0 -1 -1 0 0 -1 -1 0 0 0 1 0 0 4 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 0 0 10 13 10 10 12 2 -1 -1 0 0 0 -1 -1 2 0 0 -1 -1 -1 -1 0 0 0 0 0 4 -1 -1 -1 -1 0 0 0 -1 0 0 -1 -1 -1 0 0 0 0 0 0 0 0 2 0 1 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 -1 0 0 -1 0 -1 0 0 0 0 0 0 0 0 2 -1 0 0 0 0 2 0 0 0 -1 -1 0 3 0 0 0 0 0 0 0 0 0 0 0 0 5 6 12 11 8 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 4
1 4 1 5 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 2 12 3 12 4 11 4 10 4 9 4 8 4 7 5 7 6 7 7 7 8 7 9 7 10 7 11 7 10 13 9 13 8 13 7 12 6 12 5 12 4 12 3 12 2 12 1 11 1 10 1 9 1 8 5 6 6 6 7 6 8 7 8 6 9 5 9 4 8 3 7 4 6 4 5 4 4 3 3 4 2 5 1 6 0 7 0 8 1 9 6 4 6 5 6 6 6 7 6 8 7 7
Time Limit: 10
Memory Limit: 256
Source Limit:
