ZOJ Problem Set - 3250
Have you played the game Chain Factor? It is a simple game played in a m-row n-column board. In each step you will be given a disc labeled with a specified number. You can place the specified disc in any column you like as long as that column is not full. The disc will land on the bottom of a column if the column is empty, or it will land on the top of the topmost disc in the column. Whenever the number on a disc matches the size of the row (horizontal group) or column (vertical group) that disc is in, it will disappear, and the number on the disc will be added into your score. If you have no column to put new disc or there is no more new disc, the game is over.
For example, if your board is like Figure 1 and you are given a disc labeled 4, you can place it in Column 3. Since there are four discs connected with the two discs labeled 4 in the row (Figure 2), the two discs disappear (Figure 3) and you get 8 points for your score. Then the disc labeled 2 matches the size of the row group (or the column group, please note that the lonely "6" does not count towards the size of this group), and the disc disappeared (Figure 4) with 2 points added into your score. Then does the disc labeled 1(Figure 5) and you score 1 point more. So you will score 8 + 2 + 1 = 11 points in total if you place the new disc in Column 3.
Initially your score is 0. The more discs you remove, the more score you get. However it is very hard to find an overall best strategy for the game. To simplify the problem, you can maximize your score in each step you move. If two or more columns lead to the same maximum score, we always choose the column that has less discs. If there is still a tie, we choose the leftist one.
Given a sequence of numbers that on discs, you need to calculate your score if you play the game in this strategy.
The input contains no more than 40 test cases. For each case there are 3 parts. The first line contains 3 numbers m, n and d (0 < m, n ≤ 20, 0 ≤ d ≤ 400). Then m * n integers indecating the initial state of game board. The jth integer in ith line is the number of jth column of ith row in original board, and -1 means an empty grid. You can assume that all integers in the initial board are between 1 and 20 inclusive or -1, and no disc will disappear in the initial state. Then d numbers s1, s2, ..., sd ( 1 ≤ si ≤ 20 ) followed in next line, which is the sequence of numbers on the discs given.
For each case you should output a line contains the score you get with the strategy described above.
5 4 1 -1 -1 -1 -1 -1 -1 -1 7 -1 2 -1 7 1 4 -1 6 5 5 7 6 4
Author: LI, Cheng
Source: ZOJ Monthly, September 2009