0

已经花了几个小时（因为我还在学习），所以也许你们可以提供帮助。问题是我无法弄清楚如何将二维数组划分为所有可能的 nxn 正方形。我正在随机化二维数组，可以说是这样的：

1 0 1   
0 2 2    
3 5 1

这个矩阵有 5 nxn 个正方形 4-2x2 和 1-3x3

目标是将所有这些正方形作为一个单独的数组一个一个地提供给函数。

ps对不起英语不好

简化：

我输入这个数组：

char array[9] = {1,0,1,0,2,2,3,5,1};

并希望将以下数组传递给函数：

char array[9] = {1,0,1,0,2,2,3,5,1};
char array[4] = {1,0,0,2};
char array[4] = {0,1,2,2};
char array[4] = {0,2,3,5};
char array[4] = {2,2,5,1};

如何从主矩阵中提取这些子矩阵？

4

2 回答 2

1

The usual way to achieve this is to supply a row/column offset and a size:

void DisplaySubArray( int arr[3][3], int x0, int y0, int size ) 
{
    int x, y, *row;

    for( y = 0; y < size; y++ )
    {
        row = &arr[y0+y][x0];
        for( x = 0; x < size; x++ )
        {
            printf( "\t%d", row[x] );
        }
        printf( "\n" );
    }
}

And the enumeration:

const int N = 3;
int arr[3][3] = { 1, 0, 1, 0, 2, 2, 3, 5, 1 };
int x0, y0, size;

for( size = 2; size <= N; size++ )
{
    for( y0 = 0; y0 <= N-size; y0++ )
    {
        for( x0 = 0; x0 <= N-size; x0++ )
        {
            printf( "%dx%d at position (%d,%d):\n", size, size, x0, y0 );
            DisplaySubArray( arr, x0, y0, size );
        }
    }
}
于 2013-06-03T23:57:45.417 回答
0

我认为在这种情况下使用递归算法是最好的方法。

让我们想象一下。您有矩阵 MxN，并且您已经处理了 MxN 的所有子矩阵。此时我们需要将解决方案扩展到矩阵 (M+1)xN - 大小相同，但多一列或一行。

事实上，我们需要在我们的子矩阵中添加一些其他子矩阵的数量，但我们可以很容易地做到这一点。看看下面：

ABC
DEF
GHI

延伸到

ABCX
DEFY
GHIZ

我们只需要添加 XY 和 YZ 子矩阵（子矩阵，在右侧以 XY 和 YZ 结尾），也许你需要在 X,Y,Z 子矩阵中，我不知道（我在主题开始帖子中没有看到它们）。因此，事实上，我们可以很容易地获得所有必要的右侧（例如，for{for{}} 循环）以用于一般解决方案（对于任何 N）。最后，再添加一个循环（从 A 列到 C 或 X 列）。

我想很明显我们得到了所有子矩阵，这些子矩阵是由于 MxN -> (M+1)xN 动作而出现的。

最终解决方案 - 我们从一些基本子矩阵（1x1、2x2，如您所愿）开始，并为每个维度扩展一个。

于 2013-06-07T00:12:12.520 回答