我有一个nxm个由非负整数组成的矩阵。例如:
2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4
“投下炸弹”会使目标细胞及其所有八个邻居的数量减少一个，直到最小值为零。
x x x
x X x
x x x
什么样的算法可以确定将所有细胞减少到零所需的最少炸弹数量?
B选项(因为我不是一个细心的读者)
事实上，问题的第一个版本并不是我要寻找的答案。我没有仔细阅读整个任务，有额外的约束条件，让我们说:
那么简单的问题是，当行中的序列必须是非递增的:
8 7 6 6 5是可能的输入序列
7 8 5 5 2是不可能的，因为7 -> 8在一个序列中增长。
也许为“简单”的问题找到答案会有助于为更难的问题找到解决方案。
PS:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
这是部分答案，我试图找到一个下界和上界，可能是炸弹的数量。
在3x3和更小的板上，解决方案通常是编号最大的单元。
在大于4x4的板中，第一个明显的下界是角的和:
*2* 3 7 *1*
1 5 6 2
2 1 3 2
*6* 9 6 *4*
无论你如何安排炸弹，都不可能用少于2+1+6+4=13个炸弹来清除这个4x4板。
在其他回答中已经提到，将炸弹放置在第二个角落以消除角落并不比将炸弹放置在角落本身更糟糕，所以考虑到棋盘:
*2* 3 4 7 *1*
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
*6* 9 1 6 *4*
我们可以通过在第二个角上放置炸弹来将角归零，从而得到一个新的板:
0 1 1 6 0
0 3 0 5 1
2 1 1 1 0
2 1 2 4 1
0 0 0 0 0
0 0 0 0 0
0 3 0 2 0
到目前为止一切顺利。我们需要13枚炸弹才能清空角落。
现在观察下面标记的数字6、4、3和2:
0 1 1 *6* 0
0 3 0 5 1
2 1 1 1 0
*2* 1 2 *4* 1
0 0 0 0 0
0 0 0 0 0
0 *3* 0 2 0
我们无法使用一枚炸弹去轰炸任何两个细胞，所以最小炸弹数量增加了6+4+3+2，所以再加上我们用来清除角落的炸弹数量，我们得到这张地图所需的最小炸弹数量变成了28枚炸弹。用少于28个炸弹是不可能清除这张地图的，这是这张地图的下限。
可以用贪心算法建立上界。其他答案表明，贪婪算法产生的解决方案使用28个炸弹。因为我们之前已经证明了没有一个最优解可以拥有少于28个炸弹，所以28个炸弹确实是一个最优解。
当贪心和我上面提到的寻找最小界的方法不收敛时，我猜你必须回去检查所有的组合。
求下界的算法如下:
选一个数值最大的元素，命名为P。 将所有距离P和P本身两步远的单元格标记为不可拾取。 将P添加到最小值列表中。 重复步骤1，直到所有单元格都不可拾取。 对最小值列表求和得到下界。
其他回答
这是对第一个问题的回答。我没有注意到他改变了参数。
创建一个所有目标的列表。根据掉落物品(掉落物品本身和所有邻居)影响的正数值的数量为目标分配一个值。最高值是9。
根据受影响目标的数量(降序)对目标进行排序，对每个受影响目标的和进行二次降序排序。
向排名最高的目标投掷炸弹，然后重新计算目标，直到所有目标值都为零。
同意，这并不总是最优的。例如,
100011
011100
011100
011100
000000
100011
这种方法需要5枚炸弹才能清除。最理想的情况是，你可以在4分钟内完成。不过,很 非常接近，没有回头路。在大多数情况下，这将是最优的，或者非常接近。
使用原来的问题数，该方法解决28个炸弹。
添加代码来演示这种方法(使用带有按钮的表单):
private void button1_Click(object sender, EventArgs e)
{
int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3},
{17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
{ 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
{ 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
{ 3, 9, 10, 13, 8, 9, 12, 12, 6, 18},
{16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
{ 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
{ 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
{ 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
{ 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};
int value = 0;
List<Target> Targets = GetTargets(matrix);
while (Targets.Count > 0)
{
BombTarget(ref matrix, Targets[0]);
value += 1;
Targets = GetTargets(matrix);
}
Console.WriteLine( value);
MessageBox.Show("done: " + value);
}
private static void BombTarget(ref int[,] matrix, Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[a, b] > 0)
{
matrix[a, b] -= 1;
}
}
}
}
}
Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
}
private static List<Target> GetTargets(int[,] matrix)
{
List<Target> Targets = new List<Target>();
int width = matrix.GetUpperBound(0);
int height = matrix.GetUpperBound(1);
for (int x = 0; x <= width; x++)
{
for (int y = 0; y <= height; y++)
{
Target t = new Target();
t.x = x;
t.y = y;
SetTargetValue(matrix, ref t);
if (t.value > 0) Targets.Add(t);
}
}
Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
return Targets;
}
private static void SetTargetValue(int[,] matrix, ref Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[ a, b] > 0)
{
t.value += 1;
t.sum += matrix[a,b];
}
}
}
}
}
}
你需要的一个类:
class Target
{
public int value;
public int sum;
public int x;
public int y;
}
蛮力!
我知道它效率不高，但即使你找到了一个更快的算法，你也可以对这个结果进行测试，以了解它有多准确。
使用一些递归，像这样:
void fn(tableState ts, currentlevel cl)
{
// first check if ts is all zeros yet, if not:
//
// do a for loop to go through all cells of ts,
// for each cell do a bomb, and then
// call:
// fn(ts, cl + 1);
}
你可以通过缓存来提高效率，如果不同的方法导致相同的结果，你不应该重复相同的步骤。
阐述:
如果轰炸单元格1,3,5的结果与轰炸单元格5,3,1的结果相同，那么，对于这两种情况，您不应该重新执行所有后续步骤，只需1就足够了，您应该将所有表状态存储在某个地方并使用其结果。
表统计信息的散列可以用于快速比较。
这是部分答案，我试图找到一个下界和上界，可能是炸弹的数量。
在3x3和更小的板上，解决方案通常是编号最大的单元。
在大于4x4的板中，第一个明显的下界是角的和:
*2* 3 7 *1*
1 5 6 2
2 1 3 2
*6* 9 6 *4*
无论你如何安排炸弹，都不可能用少于2+1+6+4=13个炸弹来清除这个4x4板。
在其他回答中已经提到，将炸弹放置在第二个角落以消除角落并不比将炸弹放置在角落本身更糟糕，所以考虑到棋盘:
*2* 3 4 7 *1*
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
*6* 9 1 6 *4*
我们可以通过在第二个角上放置炸弹来将角归零，从而得到一个新的板:
0 1 1 6 0
0 3 0 5 1
2 1 1 1 0
2 1 2 4 1
0 0 0 0 0
0 0 0 0 0
0 3 0 2 0
到目前为止一切顺利。我们需要13枚炸弹才能清空角落。
现在观察下面标记的数字6、4、3和2:
0 1 1 *6* 0
0 3 0 5 1
2 1 1 1 0
*2* 1 2 *4* 1
0 0 0 0 0
0 0 0 0 0
0 *3* 0 2 0
我们无法使用一枚炸弹去轰炸任何两个细胞，所以最小炸弹数量增加了6+4+3+2，所以再加上我们用来清除角落的炸弹数量，我们得到这张地图所需的最小炸弹数量变成了28枚炸弹。用少于28个炸弹是不可能清除这张地图的，这是这张地图的下限。
可以用贪心算法建立上界。其他答案表明，贪婪算法产生的解决方案使用28个炸弹。因为我们之前已经证明了没有一个最优解可以拥有少于28个炸弹，所以28个炸弹确实是一个最优解。
当贪心和我上面提到的寻找最小界的方法不收敛时，我猜你必须回去检查所有的组合。
求下界的算法如下:
选一个数值最大的元素，命名为P。 将所有距离P和P本身两步远的单元格标记为不可拾取。 将P添加到最小值列表中。 重复步骤1，直到所有单元格都不可拾取。 对最小值列表求和得到下界。
这个贪婪的解决方案似乎是正确的:
正如评论中指出的那样，它在2D中会失败。但也许你可以改进它。
1 d: 如果至少有2个数字，你不需要从最左边的那个开始射击，因为从第二个开始射击并不差。所以射到第二个，而第一个不是0，因为你必须这么做。移动到下一个单元格。不要忘记最后一个单元格。
c++代码:
void bombs(vector<int>& v, int i, int n){
ans += n;
v[i] -= n;
if(i > 0)
v[i - 1] -= n;
if(i + 1< v.size())
v[i + 1] -= n;
}
void solve(vector<int> v){
int n = v.size();
for(int i = 0; i < n;++i){
if(i != n - 1){
bombs(v, i + 1, v[i]);
}
else
bombs(v, i, v[i])
}
}
对于2D: 再次强调:你不需要在第一行拍摄(如果有第二行)。所以要射到第二个。解决第一行的1D任务。(因为你需要使它为空)。下降。别忘了最后一排。
永远不要轰炸边界(除非正方形没有边界以外的邻居) 零角落。 到零角，将对角线上一个正方形的角的值降低(唯一的非边界邻居) 这会产生新的角落。见第2节
编辑:没有注意到Kostek提出了几乎相同的方法，所以现在我提出了更强烈的主张: 如果要清除的角总是选择在最外层，那么它是最优的。
在OP的例子中:在除5之外的任何地方掉落2(1+1或2)并不会导致掉落5所能击中的任何方块。所以我们必须在5上加上2(在左下角加上6…)
在这之后，只有一种方法可以清除(在左上角)角落里原本是1(现在是0)的东西，那就是在B3上删除0(类似excel的符号)。 等等。
只有在清除了整个A和E列以及1和7行之后，才开始更深一层的清理。
考虑只清除那些故意清除的角落，清除0值的角落不需要花费任何成本，并且简化了思考。
因为所有以这种方式投掷的炸弹都必须被投掷，并且这将导致清除战场，这是最佳解决方案。
睡了一觉后，我意识到这不是真的。 考虑
ABCDE
1 01000
2 10000
3 00000
4 00000
我的方法是在B3和C2上投放炸弹，而在B2上投放炸弹就足够了
