P3866 [TJOI2009] War Game

Xiao R is playing a war game. The map is an $M$-row, $N$-column grid. Each cell may be an obstacle or empty. At the start of the game, several enemy units are scattered across different empty cells. Each enemy unit can move from its current cell to one of the four adjacent cells, but it cannot move into a cell that contains an obstacle. If an enemy unit moves outside the map boundary, the war is lost.

Before the enemies start moving, your task is to use airstrikes to turn some originally empty cells into impassable cells, which may prevent the enemies from leaving the map. For special reasons, you cannot bomb any cell currently occupied by an enemy unit. Due to terrain differences, the amount of explosives needed to bomb each empty cell into an impassable cell may vary. You need to compute the minimum total amount of explosives required to prevent the enemies from moving out of the map boundary.

The first line contains two integers $M$ and $N$, the numbers of rows and columns of the grid. The next $M$ lines each contain $N$ space-separated integers, describing the grid cells: - If the number is $-1$, the cell is an obstacle. - If the number is $0$, there is an enemy unit in this cell. - If the number is a positive integer $x$, the cell is empty, and $x$ units of explosives are needed to bomb it into an impassable cell. The number of enemy units on the map is not equal to $1$ (i.e., there are at least two cells with $0$).

Output a single number: the minimum total amount of explosives required. The testdata guarantee that a solution exists.

- For 50% of the testdata, $1 \le M, N \le 10$. - For 100% of the testdata, $1 \le M, N \le 30$. - Every number in the matrix does not exceed $100$. Translated by ChatGPT 5