andMcolumns. The rows are numbered from 1 toNfrom top to bottom, and the columns are numbered
from 1 to Mfrom left to right. Each cell in the grid has unlimited store of a certain type of sugar, each
unit of sugar gives the player a specic score. The game is just 1 step, given 1 super ant, position it in
any cell in the grid, and the ant will do its magical work to determine your score.
Once a super ant is placed in one of the cells, it does a systematic behavior to gather sugar units from
the stores. If there is no remaining time, the ant gets 1 unit of sugar from the store of its cell and stops
working. If there is some remaining time, it starts a magical operation, which is the ants cloning operation.
The super ant starts to clone itself to all the possible cells according to the current remaining time (all of
its cloning operations start at the same time). It takes Dseconds to clone itself to a cell that is far with
Dunits. An ant at position (R1, C1) is far from the position (R2, C2) by max(|R1- R2|, |C1- C2|) units
(where |X| means the absolute value of X). Once a new super ant is cloned, it behaves as a super ant
by utilizing the remaining time.
At the end, when the remaining time is not enough for any ant to clone itself to any other cell, each ant
will collect one unit of sugar from its cell and your score is the sum of the values of all the collected sugar
units. Note that an ant can not clone itself to another cell with distance more than the current remaining
time, and an ant can not clone itself to the same cell more than once, and it can not clone itself to its
cell, and any cell can contain any number of ants at any time.
Okay, which positions an ant can clone itself to them? First of all, an ant can not clone itself to a cell
outside of the grid. Second, it can only clone to any cell in one of its 8 directions' vectors. Direction
vector means all consecutive cells on the same direction, for example from position (A, B), east vector
will generate (A, B+ 1), (A, B+ 2), (A, B+ 3) and so on. In the below image, a super ant with 2
seconds remaining, can clone itself to 16 positions, 8 of them with distance 1 and 8 with distance 2.
Given the score value of each sugar unit in the grid, the total allowed time you have (the time starts once
the rst ant is placed) and a cell which the rst super ant will start from it, can you write a program
which calculates the score you will get if you used that cell?