P2566 [SCOI2009] Enclosing Beans

Sichuan NOI2009 NOI Qualifier.

Are you tired of playing Pac-Man on your phone? Recently, the MOKIA phone launched a new game called “Enclosing Beans.” Give it a try. The rules are simple. In an $N\times M$ grid there are $D$ beans, and each bean has a value $V_i$. The player may choose any cell as the starting cell. Each move, the player may go to one of the four orthogonally adjacent cells, and eventually must return to the starting cell. The final score is the total value of all beans enclosed by the path minus the number of steps taken. Some cells contain obstacles; at no time may the player enter a cell that contains an obstacle or a bean. The player’s minimum possible score is $0$, i.e., they may choose to do nothing. Note the notion of being enclosed: a bean is considered enclosed if it lies inside the polygon formed by the path (which may be a complex polygon with self-intersections). See the two examples below:  In the first example, the bean lies inside the rectangle formed by the path, so it is enclosed. In the second example, even though the path visits the $8$ neighboring cells around the bean, the interior of the polygon formed by the path does not contain the bean, so it is not enclosed. Bubu has become obsessed with this game but cannot get a high score. You decide to write a program to help him pass the game.

The first line contains two integers $N$ and $M$, the dimensions of the grid. The second line contains an integer $D$, the total number of beans. The third line contains $D$ integers $V_1$ to $V_D$, the values of the beans. Then follow $N$ lines, each with $M$ characters, forming an $N\times M$ character matrix describing the game grid. Character `0` denotes an empty cell, `#` denotes an obstacle, and digits `1` to `9` denote beans with the corresponding indices.

Output a single integer, the maximum possible score.

$50\%$ of the testdata satisfies $1\le D\le 3$. $100\%$ of the testdata satisfies $1\le D\le 9$, $1\le N,M\le 10$, $-10^4\le V_i\le 10^4$. Translated by ChatGPT 5