题目描述(ID:12035)

标题: 宝岛探险
详情:
小哼通过秘密方法得到一张不完整的钓鱼岛航拍地图。钓鱼岛由一个主岛和一些附属岛屿组成，小哼决定去钓鱼岛探险。下面这个10*10的二维矩阵就是钓鱼岛的航拍地图。图中数字表示海拔，0表示海洋，1~9都表示陆地。小哼的飞机将会降落在(6,8)处，现在需要计算出小哼降落所在岛的面积（即有多少个格子）。注意此处我们把与小哼降落点上下左右相链接的陆地均视为同一岛屿。
1
2
1
0
0
0
0
0
2
3
3
0
2
0
1
2
1
0
1
2
4
0
1
0
1
2
3
2
0
1
3
2
0
0
0
1
2
4
0
0
0
0
0
0
0
0
1
5
3
0
0
1
2
1
0
1
5
4
3
0
0
1
2
3
1
3
6
2
1
0
0
0
3
4
8
9
7
5
0
0
0
0
0
3
7
8
6
0
1
2
0
0
0
0
0
0
0
0
1
0
限制: n<=100
m<=100
样例:

输入

10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0

输出

38


思路：

就是求一个图中独立子图的个数。对于每个岛都对它进行标号，然后从第一个点开始满水灌溉，它所能淹到的点都被标记成了这个点所特有的标号（用负号来标记，因为数大于0表示它还没有被灌过）。这里的思想就是Floodfill漫水填充法（也叫种子填充法）。比如什么windows的画图工具啊 PS里面的什么魔术棒选择工具啊，都是基于这个算法的实现。


代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
  
struct note
{
    int x;
    int y;
} ;
  
int main()
{
    //freopen("in.txt","r",stdin); 
    struct note que [10001];
    int head,tail;
    int a[1000][1000];
    int book[1000][1000]={0};
    int sum=0,maxn=0,mx,my,n,m,startx,starty,tx,ty;
    int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
    scanf("%d%d%d%d",&n,&m,&startx,&starty);
      
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
     
    if(a[startx][starty]!=0&&a[startx-1][starty]==0&&a[startx][starty+1]==0&&a[startx][starty-1]==0&&a[startx+1][starty]==0)
    {
        printf("1\n");
        return 0;
    } 
              
    head=1;
    tail=1;
    que[tail].x=startx;
    que[tail].y=starty;
    tail++;
    book[startx][starty]=1;
    sum++;
      
    while(head<tail)
    {
        for (int k=0;k<=3;k++)
        {
            tx=que[head].x+next[k][0];
            ty=que[head].y+next[k][1];
            if(tx<1||tx>n||ty<1||ty>n)continue;
            if(a[tx][ty]>0&&book[tx][ty]==0)
            {
                sum++;
                book[tx][ty]=1;
                que[tail].x=tx;
                que[tail].y=ty;
                tail++; 
            }
        }
        head++;
    }
    printf("%d\n",sum);
    return 0;
}