检查二维数组中的连接

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;