北航　机试　小岛面积

小岛面积
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
上面矩阵的中的 1 代表海岸线,0 代表小岛。求小岛面积(即被 1 中包围的 0 的个数)。注意:
仅求这样的 0,该 0 所在行中被两个 1 包围,该 0 所在列中被两个 1 包围。
输入:
第一行输入一个整数 N,表示输入方阵的维数
输入一个 N 维方阵
输出:
小岛面积
样例输入:
6
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
样例输出:
8

思路

理解题目本身意思,可以发现对于矩阵中的 0 是否属于内陆,取决于该 0 所处的行和列上,
如果 0 满足,如下条件则 O 为内陆,否则不是。
0 所在的行,0 的左边和右边必须有 1
0 所在的列,0 的上面和下面必须有 1
所以,解题思路就是,遍历所有的行和列,记录改行或列,最左面和最右面(或者最上面和
最下面)1 的坐标,然后当遇到 0,判断是否处于记录的值的中间,是,则是内陆,面积加 1,
否则不加。

代码

#include <stdio.h>
#define M 100


int caculateArea(int l[M][M],int n){
    int row[M][2]; // left 1 anf right 1  of erery row
    int col[M][2]; // top 1 and bottom 1 of every col
    for(int i=0;i<n;i++){
        row[i][0] = n;
        row[i][1] = -1;
        col[i][0] = n;
        col[i][1] = -1;
    }
    int area = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(l[i][j] != 0){

                if(row[i][0] == n){
                    row[i][0] = j;
                }
                else{
                    row[i][1] = j;
                }

                if(col[j][0] == n){
                    col[j][0] = i;
                }
                else{
                    col[j][1] = i;
                }
            }
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(l[i][j] == 0){

                if(j<row[i][1] && j>row[i][0] && i<col[j][1] && i>col[j][0]){
                    area++;
                }

            }
        }
    }
    return area;
}

int main() {

    int n;// matrix's row and column length
    int land[M][M];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&land[i][j]);
        }
    }

    printf("%d",caculateArea(land,n));
    return 0;
}

/*
6
1 1 1 1 1 1
1 1 0 0 0 1
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1*/

疑问

对于如下数据
6
1 1 1 1 1 1
1 1 0 0 0 0
1 0 0 0 1 0
1 1 0 1 1 1
0 1 0 1 0 0
1 1 1 1 1 1
对于　斜体的　０　相连的区域　算是小岛吗

本来打算用并查集做的　但是发现题目中的要求好像不太符合　　比如我上面说的情况