檢查二維數組中的連接

Question

所以我有一個正方形的二維數組。尺寸將是nxn。該數組只包含零和1。更具體地說，它將包含n 1。我需要檢查所有的1是否在空間上「連接」。例如：

0 0 0 0 
    1 1 1 0 
    0 0 0 1 
    0 0 0 0 

這是無效的。對角線連接不計數。到目前爲止，我的代碼將檢查數組，但僅用於唯一的單個1。如果1被分成兩組，例如，我的支票就會錯過它。任何建議表示讚賞。 這裏是我到目前爲止的代碼：

int conected(char *stringptr) 
    { 
int n=sqrt(strlen(stringptr)); 
int i=0; 
int j=0; 
int k=0; 
char array2d[n][n]; 

for (j=0;j<n;j++) { 
    for (i=0;i<n;i++) { 
     array2d[j][i]=stringptr[k]; 
     k++; 
    } 
} 

for (j=0;j<n;j++) { 
    for (i=0;i<n;i++) { 
     if (array2d[j][i]=='1') { 
      if (i==0 && j==0) {//special case for first element 
       if ((array2d[j][i+1]=='0') && (array2d[j+1][i]=='0')) { 
        return 0; 
       } 
      } 
      else if ((j==0) && (i!=(n-1))) {//top row 
       if ((array2d[j][i+1]=='0') && (array2d[j+1][i]=='0') && (array2d[j][i-1]=='0')) { 
        return 0; 
       } 
      } 
      else if ((j==0) && (i==(n-1))) {// right corner 
       if ((array2d[j+1][i]=='0') && (array2d[j][i-1]=='0')) { 
        return 0; 
       } 
      } 
      else if ((i==0) && (j!=(n-1))) { //left column 
       if ((array2d[j][i+1]=='0') && (array2d[j+1][i]=='0') && (array2d[j-1][i]=='0')) { 
        return 0; 
       } 
      } 
      else if ((i==(n-1)) && (j!=(n-1))) {// right column 
       if ((array2d[j][i-1]=='0') && (array2d[j+1][i]=='0') && (array2d[j-1][i]=='0')) { 
        return 0; 
       } 
      } 
      else if ((i==0) && (j==(n-1))) {//bottom left corner 
       if ((array2d[j][i+1]=='0') && (array2d[j-1][i]=='0')) { 
        return 0; 
       } 
      } 
      else if ((j==(n-1)) && (i!=(n-1))) {//bottom row 
       if ((array2d[j][i+1]=='0') && (array2d[j-1][i]=='0') && (array2d[j][i-1]=='0')) { 
        return 0; 
       } 
      } 
      else if ((j==(n-1)) && (i==(n-1))){ //bottom right corner 
       if ((array2d[j][i-1]=='0') && (array2d[j-1][i]=='0')) { 
        return 0; 
       } 
      } 
      else { 
       if ((array2d[j][i-1]=='0') && (array2d[j+1][i]=='0') && (array2d[j-1][i]=='0') && (array2d[j][i+1]=='0')) { 
        return 0; 
       } 
      } 
     } 
    } 
} 
return 1; 

}

Answer 1

一些建議：

• 一旦你找到了第一個1，你可以在列表中的好鄰居（是1太）存儲，所以你可以訪問那些（哦，這是C和你沒有列表方便，只是使用 n大小的陣列），否則你可以使用遞歸（實際上這將是棘手和有趣的）
• 你知道，有ñ 1秒，這意味着，一旦你找到一個你必須找到剩餘n-1和同組內：如果您發現該組較小比ň那麼你就可以返回假
• 您可以使用偏移合併方向（例如 int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}，這將是更優雅且不易出錯，然後您可以遍歷方向

我可以爲您提供僞代碼，但它會被欺騙，你知道..

只是遞歸的緣故：一個n-sized如果一個單獨的1連接到一個大小爲的n-1，那麼將連接1組。這應該指向正確的方向。

Answer 2

從一個數組開始，跟蹤四個單獨的二維變量，以將'1's的位置保存在數組中。這將使驗證很簡單：

int coords[4][2] = {0}; 

你還需要一個計數器，以確保只有4 '1'座標中發現：

int count = 0; 

我還建議定義爲便於閱讀，一些常量：

const int X = 0; 
const int Y = 1; 

然後通過您的數組循環查找所有'1'的實例。如果count超過4或小於4，則失敗。

for (int x = 0; x < 4; x++) 
{ 
    for (int y = 0; y < 4; y++) 
    { 
    if (array2d[x][y] == '1') 
    { 
     if (count < 4) // Make sure the 4 instances have not yet been found. 
     { 
     // Save the instance. 
     coords[count][X] = x; 
     coords[count][Y] = y; 
     } 

     if (++count > 4) // Increments count and then checks if greater than 4. 
     { 
     return false; 
     } 
    } 
    } 
} 

if (count != 4) 
{ 
    return false; 
} 

接下來，循環遍歷所在實例的數組，檢查索引偏移量以驗證它們全部相鄰。只要找到不相鄰的索引，就會失敗。下面的例子使用我們的count變量，因爲它應該在4這個點上，只要它們都被覆蓋了，我們是否以相反的順序遍歷實例並不重要。此外，這是偉大的代碼重用。（：

int x1, y1, x2, y2; 

do 
{ 
    count--; // decrement count so index offset is valid 
    x1 = coords[count][X]; 
    y1 = coords[count][Y]; 
    x2 = coords[count-1][X]; 
    y2 = coords[count-1][Y]; 

    // Check for fail condition . . . 
    if ((abs(x1 - x2) != 1) && (abs(y1 - y2) != 1)) 
    { 
    // Both the X and Y coordinates of the two instances, 
    // which should be adjacent, are greater than 1; fail. 
    return false; 
    } 
} 
while (count > 0); 
// Each time through loop count will equal 3, 2, 1, and then exit. 

在上面的例子中，我們不希望通過循環與count == 0運行，因爲0偏移被選中時count==1最後，如果PC使得它通過循環而不失效，我們。知道的'1'正好4個實例中發現，他們都是相鄰;成功：？

return true;