北航　机试　小岛面积

北航　机试　小岛面积

小岛面积
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 100int caculateArea(int l[M][M],int n){int row[M][2]; // left 1 anf right 1  of erery rowint col[M][2]; // top 1 and bottom 1 of every colfor(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 lengthint 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
对于　斜体的　０　相连的区域　算是小岛吗

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