4019. Turtle restoring

The turtle wants to pass the rectangular table as quickly as possible from top left corner to bottom right corner along the route with the least losses.

Input. The first line contains two positive integers n and m (n, m ≤ 1000) – the size of the table. Each of the next n lines contains m integers – the description of the table, each cell contains the amount of acid in it (in milliliters).

The turtle can move only one cell down or right.

Output. Print in the first line the minimal possible turtle’s damage. In the next lines print the cells coordinates along which the appropriate path runs. Print the coordinates in the order like they appear on the route.

Sample input	Sample output
3 4 5 9 4 3 3 1 6 9 8 6 8 12	35 1 1 2 1 2 2 3 2 3 3 3 4

SOLUTION

dynamic programming

Algorithm analysis

Let  a[i][j] contains the amount of damage for the turtle after visiting the cell (i, j). Let dp[i][j] contains the minimum possible damage for the turtle during the route from (1, 1) to (i, j).

Consider the base cases:

· dp[1][1] = a[1][1];

· dp[i][1] = dp[i – 1][1] + a[i][1], 1 < i ≤ n (first column);

· dp[1][j] = dp[1][j – 1] + a[1][j], 1 < j ≤ m (first row);

One can get into the cell (i, j) either from (i – 1, j) or from (i, j – 1). Since the damage is minimized, then

dp[i][j] = min(dp[i – 1][j], dp[i][j – 1]) + a[i][j]

Start the movement from the right lower corner (n, m) to the left upper corner (1, 1) along the path of minimum damage. Initialize (i, j) = (n, m). From the cell (i, j) we can move either to (i – 1, j) or to (i, j – 1) depending on which of these values is less. If dp[i – 1][j] = dp[i][j – 1], then the movement can be continued into any of these two cells.

If we arrived to the cell of the first row, then we move to the corner (1, 1) along the cells of the first row. If we arrived to the cell of the first column, then we move to the corner (1, 1) along the cells of the first column.

Sample

Algorithm realization

Declare the arrays.

#define MAX 1010

int a[MAX][MAX], dp[MAX][MAX];

Read the input data.

scanf("%d %d", &n, &m);

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

scanf("%d", &a[i][j]);

Initialize the first row and the first column of array dp.

dp[1][1] = a[1][1];

for (i = 2; i <= n; i++)

dp[i][1] = dp[i - 1][1] + a[i][1];

for (j = 2; j <= m; j++)

dp[1][j] = dp[1][j - 1] + a[1][j];

Find the minimum possible damage for the turtle for each cell.

for (i = 2; i <= n; i++)

for (j = 2; j <= m; j++)

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];

Print the minimum damage with which you can reach the lower right corner.

printf("%d\n", dp[n][m]);

Initialize (i, j) = (n, m). Start the movement from the right lower corner to the left upper corner.

i = n; j = m;

Continue moving until we reach the first row or first column. Push the point (i, j) into the path array.

while (i > 1 && j > 1)

{

path.push_back(make_pair(i, j));

if (dp[i - 1][j] + a[i][j] == dp[i][j]) i--; else j--;

}

Move to the cell (1, 1) either by the first row or by the first column.

while (i > 1) path.push_back(make_pair(i, j)), i--;

while (j > 1) path.push_back(make_pair(i, j)), j--;

path.push_back(make_pair(1, 1));

The path should be reversed.

reverse(path.begin(), path.end());

Print the path found.

for (i = 0; i < path.size(); i++)

printf("%d %d\n", path[i].first, path[i].second);