P3866 [TJOI2009] 战争游戏

小R正在玩一个战争游戏。游戏地图是一个M行N列的矩阵，每个格子可能是障碍物，也可能是空地，在游戏开始时有若干支敌军分散在不同的空地格子中。每支敌军都可以从当前所在的格子移动到四个相邻的格子之一，但是不能移动到包含障碍物的格子。如果敌军移动出了地图的边界，那么战争就失败了。

现在你的任务是，在敌军开始移动前，通过飞机轰炸使得某些原本是空地的格子变得不可通行，这样就有可能阻止敌军移出地图边界（出于某种特殊的考虑，你不能直接轰炸敌军所在的格子）。由于地形不同的原因，把每个空地格子轰炸成不可通行所需的炸药数目可能是不同的，你需要计算出要阻止敌军所需的最少的炸药数。

无

无

对50%的数据，1 ≤ M,N ≤ 10 对100%的数据，1 ≤ M,N ≤ 30 矩阵里的每个数不超过100