我有一个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:我相信当我们有几个相同的情况需要最少的炸弹来清除上面的线时，我们会选择在“左侧”使用最多炸弹的一个。还有什么证据是正确的吗?
当前回答
这是对第一个问题的回答。我没有注意到他改变了参数。
创建一个所有目标的列表。根据掉落物品(掉落物品本身和所有邻居)影响的正数值的数量为目标分配一个值。最高值是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;
}
其他回答
这是另一个想法:
让我们先给黑板上的每个空格分配一个权重，计算在那里扔炸弹会减少多少数字。如果这个空间有一个非零数，它就得到一个点，如果它的相邻空间有一个非零数，它就得到一个额外的点。如果这是一个1000 * 1000的网格，我们为这100万个空间中的每一个都分配了权重。
然后根据权重对列表中的空格进行排序，并轰炸权重最高的空格。可以这么说，这是我们最大的收获。
在此之后，更新每个空间的重量是受炸弹的影响。这是你轰炸的空间，和它相邻的空间，以及它们相邻的空间。换句话说，任何空间的价值都可能因为爆炸而减少为零，或者相邻空间的价值减少为零。
然后，根据权重重新排序列表空间。由于轰炸只改变了一小部分空间的权重，因此不需要使用整个列表，只需在列表中移动这些空间。
轰炸新的最高权重空间，并重复上述步骤。
这保证了每次轰炸都能减少尽可能多的空格(基本上，它会击中尽可能少的已经为零的空格)，所以这是最优的，除非它们的权重是相同的。所以你可能需要做一些回溯跟踪，当有一个平局的顶部重量。不过，只有最高重量的领带重要，其他领带不重要，所以希望没有太多的回溯。
Edit: Mysticial's counterexample below demonstrates that in fact this isn't guaranteed to be optimal, regardless of ties in weights. In some cases reducing the weight as much as possible in a given step actually leaves the remaining bombs too spread out to achieve as high a cummulative reduction after the second step as you could have with a slightly less greedy choice in the first step. I was somewhat mislead by the notion that the results are insensitive to the order of bombings. They are insensitive to the order in that you could take any series of bombings and replay them from the start in a different order and end up with the same resulting board. But it doesn't follow from that that you can consider each bombing independently. Or, at least, each bombing must be considered in a way that takes into account how well it sets up the board for subsequent bombings.
Well, suppose we number the board positions 1, 2, ..., n x m. Any sequence of bomb drops can be represented by a sequence of numbers in this set, where numbers can repeat. However, the effect on the board is the same regardless of what order you drop the bombs in, so really any choice of bomb drops can be represented as a list of n x m numbers, where the first number represents the number of bombs dropped on position 1, the second number represents the number of bombs dropped on position 2, etc. Let's call this list of n x m numbers the "key".
你可以试着先计算1个炸弹投下的所有板子状态，然后用这些来计算2个炸弹投下的所有板子状态，等等，直到你得到所有的0。但是在每一步中，您都将使用上面定义的键缓存状态，因此您可以在计算下一步时使用这些结果(一种“动态规划”方法)。
但是根据n、m的大小和网格中的数字，这种方法的内存需求可能会过多。一旦你计算了N + 1的所有结果，你就可以抛弃N个炸弹投掷的所有结果，所以这里有一些节省。当然，您不能以花费更长的时间为代价缓存任何东西——动态编程方法以内存换取速度。
你可以使用状态空间规划。 例如，使用A*(或其变体之一)加上启发式f = g + h，如下所示:
G:到目前为止投下的炸弹数量 H:网格中所有值的总和除以9(这是最好的结果，意味着我们有一个可接受的启发式)
所有这些问题都归结为计算编辑距离。简单地计算给定矩阵和零矩阵之间的Levenshtein距离的变体，其中编辑被轰炸替换，使用动态编程来存储中间数组之间的距离。我建议使用矩阵的哈希作为键。在pseudo-Python:
memo = {}
def bomb(matrix,i,j):
# bomb matrix at i,j
def bombsRequired(matrix,i,j):
# bombs required to zero matrix[i,j]
def distance(m1, i, len1, m2, j, len2):
key = hash(m1)
if memo[key] != None:
return memo[key]
if len1 == 0: return len2
if len2 == 0: return len1
cost = 0
if m1 != m2: cost = m1[i,j]
m = bomb(m1,i,j)
dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
memo[key] = dist
return dist
我想不出一个计算实际数字的方法除非用我最好的启发式方法计算轰炸行动并希望得到一个合理的结果。
So my method is to compute a bombing efficiency metric for each cell, bomb the cell with the highest value, .... iterate the process until I've flattened everything. Some have advocated using simple potential damage (i.e. score from 0 to 9) as a metric, but that falls short by pounding high value cells and not making use of damage overlap. I'd calculate cell value - sum of all neighbouring cells, reset any positive to 0 and use the absolute value of anything negative. Intuitively this metric should make a selection that help maximise damage overlap on cells with high counts instead of pounding those directly.
下面的代码在28个炸弹中达到了测试场的完全破坏(注意，使用潜在伤害作为度量，结果是31!)
using System;
using System.Collections.Generic;
using System.Linq;
namespace StackOverflow
{
internal class Program
{
// store the battle field as flat array + dimensions
private static int _width = 5;
private static int _length = 7;
private static int[] _field = new int[] {
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
};
// this will store the devastation metric
private static int[] _metric;
// do the work
private static void Main(string[] args)
{
int count = 0;
while (_field.Sum() > 0)
{
Console.Out.WriteLine("Round {0}:", ++count);
GetBlastPotential();
int cell_to_bomb = FindBestBombingSite();
PrintField(cell_to_bomb);
Bomb(cell_to_bomb);
}
Console.Out.WriteLine("Done in {0} rounds", count);
}
// convert 2D position to 1D index
private static int Get1DCoord(int x, int y)
{
if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
else
{
return (y * _width) + x;
}
}
// Convert 1D index to 2D position
private static void Get2DCoord(int n, out int x, out int y)
{
if ((n < 0) || (n >= _field.Length))
{
x = -1;
y = -1;
}
else
{
x = n % _width;
y = n / _width;
}
}
// Compute a list of 1D indices for a cell neighbours
private static List<int> GetNeighbours(int cell)
{
List<int> neighbours = new List<int>();
int x, y;
Get2DCoord(cell, out x, out y);
if ((x >= 0) && (y >= 0))
{
List<int> tmp = new List<int>();
tmp.Add(Get1DCoord(x - 1, y - 1));
tmp.Add(Get1DCoord(x - 1, y));
tmp.Add(Get1DCoord(x - 1, y + 1));
tmp.Add(Get1DCoord(x, y - 1));
tmp.Add(Get1DCoord(x, y + 1));
tmp.Add(Get1DCoord(x + 1, y - 1));
tmp.Add(Get1DCoord(x + 1, y));
tmp.Add(Get1DCoord(x + 1, y + 1));
// eliminate invalid coords - i.e. stuff past the edges
foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
}
return neighbours;
}
// Compute the devastation metric for each cell
// Represent the Value of the cell minus the sum of all its neighbours
private static void GetBlastPotential()
{
_metric = new int[_field.Length];
for (int i = 0; i < _field.Length; i++)
{
_metric[i] = _field[i];
List<int> neighbours = GetNeighbours(i);
if (neighbours != null)
{
foreach (int j in neighbours) _metric[i] -= _field[j];
}
}
for (int i = 0; i < _metric.Length; i++)
{
_metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
}
}
//// Compute the simple expected damage a bomb would score
//private static void GetBlastPotential()
//{
// _metric = new int[_field.Length];
// for (int i = 0; i < _field.Length; i++)
// {
// _metric[i] = (_field[i] > 0) ? 1 : 0;
// List<int> neighbours = GetNeighbours(i);
// if (neighbours != null)
// {
// foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
// }
// }
//}
// Update the battle field upon dropping a bomb
private static void Bomb(int cell)
{
List<int> neighbours = GetNeighbours(cell);
foreach (int i in neighbours)
{
if (_field[i] > 0) _field[i]--;
}
}
// Find the best bombing site - just return index of local maxima
private static int FindBestBombingSite()
{
int max_idx = 0;
int max_val = int.MinValue;
for (int i = 0; i < _metric.Length; i++)
{
if (_metric[i] > max_val)
{
max_val = _metric[i];
max_idx = i;
}
}
return max_idx;
}
// Display the battle field on the console
private static void PrintField(int cell)
{
for (int x = 0; x < _width; x++)
{
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
}
Console.Out.Write(" || ");
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
}
Console.Out.WriteLine();
}
Console.Out.WriteLine();
}
}
}
产生的轰炸模式输出如下(左边是字段值，右边是度量值)
Round 1:
2 1 4 2 3 2 6 || 7 16 8 10 4 18 6
3 5 3 1 1 1 9 || 11 18 18 21 17 28 5
4 [2] 4 2 3 4 1 || 19 [32] 21 20 17 24 22
7 6 2 4 4 3 6 || 8 17 20 14 16 22 8
1 2 1 1 1 2 4 || 14 15 14 11 13 16 7
Round 2:
2 1 4 2 3 2 6 || 5 13 6 9 4 18 6
2 4 2 1 1 [1] 9 || 10 15 17 19 17 [28] 5
3 2 3 2 3 4 1 || 16 24 18 17 17 24 22
6 5 1 4 4 3 6 || 7 14 19 12 16 22 8
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 3:
2 1 4 2 2 1 5 || 5 13 6 7 3 15 5
2 4 2 1 0 1 8 || 10 15 17 16 14 20 2
3 [2] 3 2 2 3 0 || 16 [24] 18 15 16 21 21
6 5 1 4 4 3 6 || 7 14 19 11 14 19 6
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 4:
2 1 4 2 2 1 5 || 3 10 4 6 3 15 5
1 3 1 1 0 1 8 || 9 12 16 14 14 20 2
2 2 2 2 2 [3] 0 || 13 16 15 12 16 [21] 21
5 4 0 4 4 3 6 || 6 11 18 9 14 19 6
1 2 1 1 1 2 4 || 10 9 10 9 13 16 7
Round 5:
2 1 4 2 2 1 5 || 3 10 4 6 2 13 3
1 3 1 1 0 [0] 7 || 9 12 16 13 12 [19] 2
2 2 2 2 1 3 0 || 13 16 15 10 14 15 17
5 4 0 4 3 2 5 || 6 11 18 7 13 17 6
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 6:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 9 12 16 11 8 13 0
2 2 2 2 0 2 0 || 13 16 15 9 14 14 15
5 4 [0] 4 3 2 5 || 6 11 [18] 6 11 15 5
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 7:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 8 10 13 9 7 13 0
2 [1] 1 1 0 2 0 || 11 [15] 12 8 12 14 15
5 3 0 3 3 2 5 || 3 8 10 3 8 15 5
1 1 0 0 1 2 4 || 8 8 7 7 9 13 5
Round 8:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 7 13 0
1 1 0 1 0 2 0 || 8 8 10 6 12 14 15
4 2 0 3 3 [2] 5 || 2 6 8 2 8 [15] 5
1 1 0 0 1 2 4 || 6 6 6 7 9 13 5
Round 9:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 6 12 0
1 1 0 1 0 [1] 0 || 8 8 10 5 10 [13] 13
4 2 0 3 2 2 4 || 2 6 8 0 6 9 3
1 1 0 0 0 1 3 || 6 6 6 5 8 10 4
Round 10:
2 1 4 2 1 0 4 || 1 7 2 4 2 10 1
0 2 [0] 1 0 0 5 || 7 7 [12] 7 6 11 0
1 1 0 1 0 1 0 || 8 8 10 4 8 9 10
4 2 0 3 1 1 3 || 2 6 8 0 6 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 11:
2 0 3 1 1 0 4 || 0 6 0 3 0 10 1
0 1 0 0 0 [0] 5 || 4 5 5 5 3 [11] 0
1 0 0 0 0 1 0 || 6 8 6 4 6 9 10
4 2 0 3 1 1 3 || 1 5 6 0 5 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 12:
2 0 3 1 0 0 3 || 0 6 0 2 1 7 1
0 1 0 0 0 0 4 || 4 5 5 4 1 7 0
1 0 0 0 0 [0] 0 || 6 8 6 4 5 [9] 8
4 2 0 3 1 1 3 || 1 5 6 0 4 7 2
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 13:
2 0 3 1 0 0 3 || 0 6 0 2 1 6 0
0 1 0 0 0 0 3 || 4 5 5 4 1 6 0
1 [0] 0 0 0 0 0 || 6 [8] 6 3 3 5 5
4 2 0 3 0 0 2 || 1 5 6 0 4 6 2
1 1 0 0 0 1 3 || 6 6 6 3 4 4 0
Round 14:
2 0 3 1 0 [0] 3 || 0 5 0 2 1 [6] 0
0 0 0 0 0 0 3 || 2 5 4 4 1 6 0
0 0 0 0 0 0 0 || 4 4 4 3 3 5 5
3 1 0 3 0 0 2 || 0 4 5 0 4 6 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 15:
2 0 3 1 0 0 2 || 0 5 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 4 4
3 1 0 3 0 [0] 2 || 0 4 5 0 4 [6] 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 16:
2 [0] 3 1 0 0 2 || 0 [5] 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 0 3 0 0 1 || 0 4 5 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 17:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 [0] 3 0 0 1 || 0 4 [5] 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 18:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 3 3 2 2 2 3 3
3 [0] 0 2 0 0 1 || 0 [4] 2 0 2 3 1
1 0 0 0 0 0 2 || 2 4 2 2 2 3 0
Round 19:
1 0 2 1 0 [0] 2 || 0 3 0 1 1 [4] 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 2 2 2 2 2 3 3
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 20:
1 [0] 2 1 0 0 1 || 0 [3] 0 1 1 2 0
0 0 0 0 0 0 1 || 1 3 3 3 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 21:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 [0] 1 || 0 2 2 0 2 [3] 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 22:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
[0] 0 0 0 0 0 0 || [2] 2 2 2 2 1 1
2 0 0 2 0 0 0 || 0 2 2 0 2 1 1
0 0 0 0 0 0 1 || 2 2 2 2 2 1 0
Round 23:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 [0] 0 0 0 1 || 0 1 [2] 2 1 2 0
0 0 0 0 0 0 0 || 1 1 2 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 24:
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 [0] 0 0 0 0 || 1 1 [2] 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 25:
0 0 0 0 0 [0] 1 || 0 0 0 0 0 [2] 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 0 || 1 1 1 1 1 1 1
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 26:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
[0] 0 0 0 0 0 0 || [1] 1 1 1 1 0 0
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 27:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 [0] 0 0 0 0 || 0 0 [1] 1 1 0 0
0 0 0 1 0 0 0 || 0 0 1 0 1 1 1
0 0 0 0 0 0 1 || 0 0 1 1 1 1 0
Round 28:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 [0] 0 || 0 0 0 0 0 [1] 1
0 0 0 0 0 0 1 || 0 0 0 0 0 1 0
Done in 28 rounds
