时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
都来看题解了，不来我博客看看嘛？链接：连通块

题目描述

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

输入描述:

第一行输入两个数字n，m（1<=n<=200，1<=m<=200）
后面n行01序列，每一行m个字符，表示陆地和海洋

输出描述:

输出一个数字表示岛屿的个数

示例1

输入

输出

解题思路

这里我提供的AC代码不是最优的，不算很简洁，因为这是基于我上一篇文章“统计岛屿个数”题目改编的代码。
我用到的算法是DFS。
了解有关DFS的内容：深度优先搜索解决连通块/染色问题——求岛的个数
这题不同的是，输入数据的时候没有空格，虽然可以存成char[]字符串形式，但是我用了另一种较为复杂的方法实现。（就是懒得改了。）

题解

#include<stdio.h>
struct note
{
    int x;
    int y;
};
struct note que[400];
int head, tail;
int a[2000][2000];//地图
int book[2000][2000];
int next[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int max = 0;
int sum = 0;
int n, m, startx, starty;

void dfs(int x, int y, int color)
{
    int k;
    int tx, ty;
    a[x][y] = color; // 对本格子染色
    for (k = 0; k < 4; k++)
    {
        tx = x + next[k][0];
        ty = y + next[k][1];
        if (tx < 1 || tx > n || ty < 1 || ty > m)
            continue;
        if (a[tx][ty] > 0 && book[tx][ty] == 0)
        {
            book[tx][ty] = 1;
            dfs(tx, ty, color);
        }
    }
    return;
}


int main()
{
    int i, j;
    int num = 0;
    char c;
    scanf("%d %d", &n, &m);
    getchar();
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            c = getchar();
            a[i][j] = c - '0';
        }
        getchar();

    }


    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (a[i][j] > 0)
            {
                num--;// num表示色号，并且是负数
                book[i][j] = 1;
                dfs(i, j, num);
            }
        }
    }
    printf("%d", -num);
    return 0;
}

题解 | #连通块#

题目描述

输入描述:

输出描述:

示例1

输入

输出

解题思路

题解