The cheapest seam
A photo editor narrows a picture by carving seams out of it. A seam is one pixel in each row, from top to bottom, with the pixels of neighbouring rows in the same column or adjacent ones. Each pixel has an energy (how much it stands out from its neighbours), and a seam’s energy is the sum of its pixels’ energies. Find the seam with the smallest energy: carving it out is the least noticeable.
If there are several such seams, print any. The third and fourth tests are the energies of real photos by the site’s author, 120 pixels wide.
Input
The first line holds the picture’s height H and width W (1 ≤ H, W; H·W ≤ 4·105). Then H lines of W integers from 0 to 1530: the pixels’ energies.
Output
The first line holds the energy of the cheapest seam. The second holds the H column numbers of this seam from top to bottom, with columns numbered from one.
Examples
Example 1
7 10 37 58 68 73 48 100 79 90 84 95 104 63 76 61 58 68 89 101 92 64 76 58 79 83 89 100 110 84 84 87 75 118 104 70 60 48 35 28 35 44 333 371 272 109 61 107 99 163 150 65 289 166 355 263 156 162 207 214 237 183 311 411 267 109 92 138 163 212 197 94
552 5 5 5 6 5 5 5
Example 2
3 3 5 1 5 5 5 1 1 5 5
7 2 1 1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A simple idea: start at the cheapest pixel of the top row and each time step to the cheapest of the three neighbours below. Check it on the first example.
2Hint 2
Suppose that for each pixel of the previous row the energy of the cheapest seam from the top to it is already known. How do you get the same for a pixel of the current row?
3The idea
M[y][x] is the energy of the cheapest seam from the top row to pixel (x, y). Such a seam comes into (x, y) from one of the three pixels above it, and up to that pixel it is itself the cheapest. So M[y][x] = E[y][x] + min(M[y−1][x−1], M[y−1][x], M[y−1][x+1]), and the answer is the smallest number in the bottom row. This is seam carving, or rather one step of it.
4Walkthrough
Fill the table row by row. Recover the seam itself from the end: stand in the cheapest cell of the bottom row and climb to whichever of the three neighbours above has the smaller M: the best seam came from it. The whole table M must be kept: the path back needs all the rows.
The greedy seam in the first example starts at the cheapest pixel, 37, goes left and at the bottom runs into the reeds on the shore: 999. The table finds a seam almost straight down the middle: 552. A cheap beginning says nothing about the continuation, and that is the reason to compute the best path to each pixel rather than a single path.
In Python it is convenient to compute a row of the table all at once: shift the previous row one cell left and right and take the element-wise minimum of the three lists.
4+Solution
5Complexity
O(H·W) time and memory: each cell is computed once from three neighbours.
6Common mistakes
- The greedy seam. Fails the first example.
- Going past the edge. Edge columns have two neighbours above, not three.
- A seam that jumps. When recovering, choose only among the three neighbours above, not the cheapest cell of the whole row.