检查二维数组中的连接

Question

所以我有一个方形二维数组。尺寸将为 nxn。该数组仅包含零和一。更具体地说，它将恰好包含 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 大小的数组)，否则你可以使用递归(实际使用起来会很棘手和有趣)
• 你确实知道有 n 个 1，这意味着一旦你找到一个，你必须在同一组中找到剩余的 n-1:如果组你发现小于 n 那么你可以返回 false
• 您可以使用偏移量合并方向(例如
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}，这样会更优雅，更不容易出错，然后您可以遍历路线

我可以为您提供伪代码，但它会作弊，您知道..

只是为了递归:如果一个 n-1 大小的组与一个 n-1 大小的组相连，那么一个 n 大小 的 1 组就是连接的。这应该会为您指明正确的方向。