北航计算机机试C12年小岛面积

【北航复试】

小岛面积
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

#include <stdio.h>
#include <string.h>

#define N 100

//both inside and outside are the valiable addresses.
int main()
{
    int br,i,j,num=0;

    int row[100][2];
    int col[100][2];
    int a[100][100];
    memset(row,-1,sizeof(row));
    memset(col,-1,sizeof(col));//compared with number 0


    scanf("%d",&br);
    for(i=0;i<br;i++)
    {
        for(j=0;j<br;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]==1)
            {
                if(row[i][0]==-1)
                    row[i][0]=j;
                if(col[j][0]==-1)
                    col[j][0]=i;
                row[i][1]=j;
                col[j][1]=i;
            }
        }
    }
    for(i=0;i<br;i++)
    {
        for(j=0;j<br;j++)
        {
            if(a[i][j]==0)
            {
                if(j>row[i][0] && j<row[i][1] && i>col[j][0] && i<col[j][1])
                {
                    num++;
                }
            }
        }
    }
    printf("%d",num);
    return 0;
}

• 小岛面积该题是一个基础的矩阵问题，算是查找吧，
• 确定每行每列的边界值
• 遍历所有的0来判断是否在该行的“墙”内，还有就是，外墙和内墙都是一样的。

不足之处，最开始定义数组时占用了100*100的内存空间，但实际不一定会用到这么多，可以用calloc来申请一定的空间，记得free()。
时间复杂度应该是o(n*n)。

p=(int*)calloc(m *n,sizeof(int));//向系统申请内存
if(p==NULL)//确保使用前是非空指针，当p为ptrnull结束程序运行
{exit(1);
}
free (p);

向系统申请了m*n个int型的存储单元，并用int型指针变量p指向这段内存的首地址，尽管它相当于建立一个二维动态数组，但因指针P是指向这个动态数组的列指针，当寻址数组元素时，必须将其当作一维数组来处理:

scanf("%d",&p[i*n+j]);
*(p+i *n+j)