Jang Hongjun the Tofu Seller
Time limit2sMemory limit128 MB
Given a grid of letter grades, tile it with non-overlapping 2x1 dominoes to maximize the sum of pairwise grade prices, leaving uncovered cells worth zero.
- Level
Hard8 of 10
- Topics
- Graph, Shortest path, Matrix, Dynamic programming
- Solved
- No attempts yet
Problem
Jang Hongjun sells tofu by cutting an N-by-M tofu board into 2 x 1 pieces. Each cell has one grade: A, B, C, D, or F. The price of a 2 x 1 piece is determined by the two grades it contains.
The price table is as follows.
The order of the two grades does not affect the price. You may cut non-overlapping 2 x 1 pieces either horizontally or vertically. Any single cell that is not included in a piece has value 0 and is discarded. Find the maximum possible total price.
Input
The first line contains the board height N and width M. N and M are integers between 1 and 14, inclusive.
Each of the next N lines contains M characters. Each character is one of A, B, C, D, and F, and represents the grade of that cell.
Output
Print the maximum possible sum of prices of the tofu pieces that are cut.