在矩阵中找到M个相邻元素的最大和的最快方法是什么 [英] Whats the fastest way to find biggest sum of M adjacent elements in a matrix
问题描述
如何找到最大的给定M？
例如，取这个矩阵4x4：
矩阵：对于M = 3对于M = 4
3 1 5 2 3 1 5 2 3 1 5 2
2 6 1 3 2 [6] 1 3 2 [6] 1 3
1 4 4 2 1 [4] [4] 2 1 [4] 4 2
5 3 2 7 5 3 2 7 [5] [3] 2 7
Biggest = 14 Biggest = 18
我试着这样做，一定的维度，很慢。
#include< bits / stdc ++。h>
using namespace std;
int mat [51] [51];
int mark [51] [51];
int m，n;
int maximum;
void search（int row，int column，int sum，int steps）{
if（row< 0 || row> = n || column< 0 || column > = n || mark [row] [column]）{
return;
}
sum + = mat [row] [column];
mark [row] [column] = 1;
if（steps == m）{
if（largest< sum）highest = sum;
}
else {
搜索（行-1，列，和，步骤+1）;
search（row + 1，column，sum，steps + 1）;
search（row，column + 1，sum，steps + 1）;
search（row，column - 1，sum，steps + 1）;
}
标记[row] [column] = 0;
}
int main（）{
memset（mat，0，sizeof（mat））;
memset（mark，0，sizeof（mark））;
largest = 0;
scanf（％d，& n）;
scanf（％d，& m）;
for（int i = 0; i
scanf d，& mat [i] [j]）;
}
}
for（int i = 0; i
search（i，j，0，1）;
}
}
printf（％d，largest）;
return 0;
}
此回答不包括代码（尚未），稍后将使用所描述的算法的实现扩展
困难是某些形状被处理多次。考虑作为填充矩形的选择。它可以从任何单元格开始并以多种不同的方式（递归路径）遍历以达到相同的选择（显然是相同的计算）。这是需要解决的问题。
为了做到这一点，你需要预先计算可以为给定的 M ，然后迭代矩阵，并为每个单元格（作为形状的左上角）计算和比较所有形状选择的总和。
预计算是通过使用递归函数完成的，就像在绘制一个（2M-1） 2 路径，从中间开始。在结束条件（选择的M个单元格）中，将生成的形状与累积的形状列表中的现有形状进行比较，并且仅在尚未存在时才添加。 需要解决+形状
优化应该在预计算阶段使用，以避免将问题从计算转移到预计算阶段， s，例如，限制遍历，使得在开始行之上是非法的（因此，形状矩阵只需要是M（2M-1）大） 。
Suppose I have a square matrix of dimension N (N <= 50) and the adjacent elements do not include the diagonals.
How can I find the biggest sum between M adjacent elements, given M?
For example, take this matrix 4x4:
Matrix: For M = 3 For M = 4
3 1 5 2 3 1 5 2 3 1 5 2
2 6 1 3 2 [6] 1 3 2 [6] 1 3
1 4 4 2 1 [4][4] 2 1 [4] 4 2
5 3 2 7 5 3 2 7 [5][3] 2 7
Biggest = 14 Biggest = 18
I tried to do this way, but after a certain dimension, it is very slow.
#include <bits/stdc++.h>
using namespace std;
int mat[51][51];
int mark[51][51];
int m, n;
int biggest;
void search(int row, int column, int sum, int steps){
if(row < 0 || row >= n || column < 0 || column >= n || mark[row][column]) {
return;
}
sum += mat[row][column];
mark[row][column] = 1;
if(steps == m){
if(biggest < sum) biggest = sum;
}
else{
search(row - 1, column, sum, steps+1);
search(row + 1, column, sum, steps+1);
search(row, column + 1, sum, steps+1);
search(row, column - 1, sum, steps+1);
}
mark[row][column] = 0;
}
int main(){
memset(mat, 0, sizeof(mat));
memset(mark, 0, sizeof(mark));
biggest = 0;
scanf("%d", &n);
scanf("%d", &m);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
scanf("%d", &mat[i][j]);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
search(i, j, 0, 1);
}
}
printf("%d", biggest);
return 0;
}
This answer does not include code (yet) and will later be extended with an implementation of the described algorithm
The main difficulty is that certain "shapes" are processed many times. Consider a selection that is a filled rectangle. It can start from any cell and traverse in multiple different ways ("recursive paths") to reach the same selection (and obviously the same calculation). It is this issue that needs to be tackled.
To do that, you need to precompute the various shapes that can be selected for the given M, then iterate the matrix and for each cell (serving as the top-left of the shape) calculate and compare the sum for all shape selections.
The precomputation is done by using a recursive function just like in the question that "paints" a (2M-1)2 matrix with the cells in the path, starting in the middle. In the end condition (M cells selected), the generated shape is compared to existing shapes in the accumulating "shapes list", and only added if it's not already there. need to solve for "+" shape scenario.
Optimizations should be used in the precompute stage to avoid " transferring" the problem from the computation to the precomputation stage for very large Ms, for example, limit traversals such that it is illegal to go above the starting row (and as a result, the shape matrix only needs to be M(2M-1) big).
这篇关于在矩阵中找到M个相邻元素的最大和的最快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
