我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
生成最慢但最简单且无错误的算法，并测试所有有效的可能性。这种情况非常简单(因为结果与炸弹放置的顺序无关)。
创建N次应用bomp的函数 为所有炸弹放置/炸弹计数可能性创建循环(当矩阵==0时停止) 记住最好的解决方案。 在循环的最后，你得到了最好的解决方案 不仅是炸弹的数量，还有它们的位置
代码可以是这样的:
void copy(int **A,int **B,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
A[i][j]=B[i][j];
}
bool is_zero(int **M,int m,int n)
{
for (int i=0;i<m;i++)
for (int j=0;i<n;j++)
if (M[i][j]) return 0;
return 1;
}
void drop_bomb(int **M,int m,int n,int i,int j,int N)
{
int ii,jj;
ii=i-1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i-1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i ; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j-1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j ; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
ii=i+1; jj=j+1; if ((ii>=0)&&(ii<m)&&(jj>=0)&&(jj<n)&&(M[ii][jj])) { M[ii][jj]-=N; if (M[ii][jj]<0) M[ii][jj]=0; }
}
void solve_problem(int **M,int m,int n)
{
int i,j,k,max=0;
// you probably will need to allocate matrices P,TP,TM yourself instead of this:
int P[m][n],min; // solution: placement,min bomb count
int TM[m][n],TP[m][n],cnt; // temp
for (i=0;i<m;i++) // max count of bomb necessary to test
for (j=0;j<n;j++)
if (max<M[i][j]) max=M[i][j];
for (i=0;i<m;i++) // reset solution
for (j=0;j<n;j++)
P[i][j]=max;
min=m*n*max;
copy(TP,P,m,n); cnt=min;
for (;;) // generate all possibilities
{
copy(TM,M,m,n);
for (i=0;i<m;i++) // test solution
for (j=0;j<n;j++)
drop_bomb(TM,m,n,TP[i][j]);
if (is_zero(TM,m,n))// is solution
if (min>cnt) // is better solution -> store it
{
copy(P,TP,m,n);
min=cnt;
}
// go to next possibility
for (i=0,j=0;;)
{
TP[i][j]--;
if (TP[i][j]>=0) break;
TP[i][j]=max;
i++; if (i<m) break;
i=0; j++; if (j<n) break;
break;
}
if (is_zero(TP,m,n)) break;
}
//result is in P,min
}
这可以通过很多方式进行优化，……最简单的是用M矩阵重置解，但你需要改变最大值和TP[][]递减代码
其他回答
这里有一个解决方案，推广良好的性质的角。
让我们假设我们可以为给定的字段找到一个完美的落点，也就是说，一个减少其中值的最佳方法。然后，为了找到最少的炸弹数量，一个算法的初稿可能是(代码是从ruby实现中复制粘贴的):
dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
coordinates = choose_a_perfect_drop_point
drop_bomb(coordinates)
dropped_bomb_count += 1
end
return dropped_bomb_count
挑战是choose_a_perfect_drop_point。首先，让我们定义一个完美的落点是什么。
(x, y)的放置点会减少(x, y)中的值。它也可能会减少其他单元格中的值。 (x, y)的放置点A比(x, y)的放置点b更好，如果它减少了b所减少的单元格的适当超集中的值。 如果没有其他更好的投放点，投放点是最大的。 (x, y)的两个放置点是等效的，如果它们减少了同一组单元格。 如果(x, y)的放置点等价于(x, y)的所有最大放置点，那么它就是完美的。
如果(x, y)存在一个完美的投放点，那么您不能比在(x, y)的一个完美投放点上投放炸弹更有效地降低(x, y)处的值。
给定字段的完美放置点是其任何单元格的完美放置点。
以下是一些例子:
1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
单元格(0,0)(从零开始的索引)的完美放置点是(1,1)。(1,1)的所有其他放置点，即(0,0)、(0,1)和(1,0)，减少的单元格较少。
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
单元格(2,2)(从零开始的索引)的完美落点是(2,2)，以及所有周围的单元格(1,1)、(1,2)、(1,3)、(2,1)、(2,3)、(3,1)、(3,2)和(3,3)。
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
单元格(2,2)的完美放置点是(3,1):它减少了(2,2)中的值和(4,0)中的值。(2,2)的所有其他放置点都不是最大的，因为它们减少了一个单元格。(2,2)的完美下拉点也是(4,0)的完美下拉点，它是字段的唯一完美下拉点。它为这个领域带来了完美的解决方案(一颗炸弹)。
1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0
(2,2)没有完美的落点:(1,1)和(1,3)都减少(2,2)和另一个单元格(它们是(2,2)的最大落点)，但它们不相等。然而，(1,1)是(0,0)的完美落点，(1,3)是(0,4)的完美落点。
根据完美落点的定义和一定的检查顺序，我得到了以下问题示例的结果:
Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28
然而，该算法只有在每一步之后至少有一个完美落点时才能工作。可以在没有完美落点的情况下构建例子:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
对于这些情况，我们可以修改算法，这样我们就不会选择完美的落点，而是选择一个具有最大落点的最小选择的坐标，然后计算每个选择的最小值。在上面的例子中，所有有值的单元格都有两个最大落点。例如，(0,1)有最大落点(1,1)和(1,2)。选择其中任何一个，然后计算最小值，会得到这样的结果:
Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2
你的新问题，有跨行不递减的值，很容易解决。
Observe that the left column contains the highest numbers. Therefore, any optimal solution must first reduce this column to zero. Thus, we can perform a 1-D bombing run over this column, reducing every element in it to zero. We let the bombs fall on the second column so they do maximum damage. There are many posts here dealing with the 1D case, I think, so I feel safe in skipping that case. (If you want me to describe it, I can.). Because of the decreasing property, the three leftmost columns will all be reduced to zero. But, we will provably use a minimum number of bombs here because the left column must be zeroed.
现在，一旦左边的列归零，我们只要剪掉最左边的三列现在归零，然后对现在化简的矩阵重复这一步骤。这必须给我们一个最优的解决方案，因为在每个阶段我们使用可证明的最少数量的炸弹。
这是对第一个问题的回答。我没有注意到他改变了参数。
创建一个所有目标的列表。根据掉落物品(掉落物品本身和所有邻居)影响的正数值的数量为目标分配一个值。最高值是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;
}
如果你想要绝对最优解来清理棋盘，你将不得不使用经典的回溯，但如果矩阵非常大，它将需要很长时间才能找到最佳解，如果你想要一个“可能的”最优解，你可以使用贪婪算法，如果你需要帮助写算法，我可以帮助你
现在想想，这是最好的办法。在那里制作另一个矩阵，存储通过投掷炸弹而移除的点，然后选择点数最多的单元格，并在那里投掷炸弹更新点数矩阵，然后继续。例子:
2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))
对于每个相邻的高于0的单元格，单元格值+1
这将是一个贪婪的方法:
计算一个阶为n X m的“score”矩阵，其中score[i][j]是如果位置(i,j)被炸毁，则矩阵中各点的总扣除额。(一个点的最高分数是9分，最低分数是0分) 逐行移动，找到并选择第一个得分最高的位置(例如(i,j))。 炸弹(i, j)。增加炸弹数量。 如果原矩阵的所有元素都不为零，则转到1。
但我怀疑这是否是最佳解决方案。
编辑:
我上面提到的贪心方法，虽然有效，但很可能不能给我们最优的解决方案。所以我想应该添加一些DP的元素。
我想我们可以同意，在任何时候，具有最高“分数”(分数[I][j] =总扣分，如果(I,j)被炸)的位置之一必须被瞄准。从这个假设开始，下面是新的方法:
NumOfBombs(M):(返回所需的最小炸弹数量)
给定一个矩阵M (n X M)，如果M中的所有元素都为0，则返回0。 计算“分数”矩阵M。 设k个不同的位置P1 P2…Pk (1 <= k <= n*m)，为m中得分最高的位置。 return (1 + min(NumOfBombs(M1)， NumOfBombs(M2)，…， NumOfBombs(Mk)) M1, M2,……，Mk是我们轰炸位置P1, P2，…， Pk。
此外，如果我们想在此基础上破坏位置的顺序，我们必须跟踪“min”的结果。
