Image Energy
Time limit2sMemory limit128 MB
Assign each grid cell to black or white to minimize per-cell cost plus adjacency mismatch cost, solvable via min-cut on a grid graph.
- Level
Medium7 of 10
- Topics
- Graph, Dynamic programming, Math
- Solved
- No attempts yet
Problem
A grayscale image consists of n×m cells, and each cell has an integer value from 0 to 255. You will approximate each cell as either black or white. The energy of an approximated image is the sum of the following values.
- If a cell with value X is approximated as black, |X - A| is added.
- If a cell with value X is approximated as white, |X - B| is added.
- For two side-adjacent cells with original values X and Y, if the two cells are approximated with different colors, |X - Y| is added.
Given the constants A and B, find the minimum possible energy over all choices of colors for the cells.
Input
The first line contains four integers n, m, A, and B. The constraints are 1 ≤ n, m ≤ 20 and 0 ≤ A, B ≤ 255.
Each of the next n lines contains m integers describing one row of the image. Each value is between 0 and 255, inclusive.
Output
Print the minimum possible energy.