將2d數組劃分爲所有可能的nxn個正方形

花費了數小時的時間（因爲我還在學習），所以也許你們可以提供幫助。問題是，我不知道如何將2d數組劃分爲所有可能的nxn方塊。我隨機二維數組讓說是這樣的：將2d數組劃分爲所有可能的nxn個正方形

1 0 1 
0 2 2  
3 5 1

有這個矩陣5個n×n的平方4-2x2和1-3x3

的目標是讓所有的方塊的功能作爲一個單獨的陣列，一個接一個。

p.s.對不起，我英文不好

簡化：

我輸入此陣：

，並希望下面的數組傳遞給函數：

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};

我怎樣才能從主矩陣中提取這些子矩陣？

來源

2013-06-03 user2449743

我編輯了你的問題了一下，因爲你其實並沒有提出問題。只講一個故事。我添加了一些澄清爲他人理解這個問題更容易:)歡迎來到Stackoverflow！ – 2013-06-03 23:52:47

您還忽略了1x1矩陣（其中樣本中有9個矩陣）。 – WhozCraig

通常的方式實現這一目標是提供一個行/列偏移量和大小：

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"); 
    } 
}

而且枚舉：

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-03 23:57:45 paddy

當你使用函數時，該算法似乎並不令人沮喪:)，非常感謝我認爲我現在明白了它，只是另外一個問題 - 如果主矩陣不是方形的，這仍然可行，我只需要給「DisplaySubArray 「函數並在main中使用一些if語句。我對嗎？ – user2449743

在這種情況下，'N'會變成兩個變量（例如'WIDTH'和'HEIGHT'）並相應地使用。不需要其他修改。 – paddy

我使用遞歸算法是認爲在這種情況下最好的辦法。

讓我們來想象一下。你有矩陣MxN，並且你已經處理了所有的MxN子矩陣。此時我們需要將我們的解決方案擴展到矩陣（M + 1）xN - 相同的大小，但是一列或一行更多。

實際上，我們需要在子矩陣中添加一些其他子矩陣的計數，但我們可以輕鬆完成。看看下面：

ABC 
DEF 
GHI

延伸到

ABCX 
DEFY 
GHIZ

我們只需添加XY和YZ子矩陣（小矩陣，這在右側結束的XY和YZ），也許你在X需要， Y，Z子矩陣，我不知道（我沒有在主題開始帖子中看到它們）。因此，事實上，我們可以很容易地獲得所有必要的正確方面（例如，{for {}}循環）解決方案（對於任何N）。最後，再添加一個循環（從A列到C或X列）。

我想很明顯，我們得到了所有由於MxN - >（M + 1）xN行爲而出現的子矩陣。最終解決方案 - 我們從一些基礎子矩陣開始（1x1,2x2，只要你喜歡），併爲每個維度擴展一個。

來源

2013-06-07 00:12:12 Boris

將2d數組劃分爲所有可能的nxn個正方形

回答

相關問題