正在给出一个satellite.The图像拍摄的表面的图像时，其中的水带标记的位图。土地的特点是' * 。相邻组 * 的形成一个小岛。 （二' * '是如果他们是水平，垂直或对角线邻域相邻）。你的任务是打印岛屿位图的数量。

You are given an image of a surface photographed by a satellite.The image is a bitmap where water is marked by '.' and land is marked by '*'. Adjacent group of '*'s form an island. (Two '*' are adjacent if they are horizontal, vertical or diagonal neighbours). Your task is to print the number of islands in the bitmap.

例输入： -

.........**
**......***
...........
...*.......
*........*.
*.........*

输出： - 5

Output:- 5

下面，是我实现它接受 O（R * C）的空间和 O（R * C）空间，其中r是总无。行和c是COLS的总无

Here, is my implementation which takes O(r * c) space and O(r * c) space where r is total no. of rows and c is total no of cols.

#include <stdio.h>
#define COLS 12

void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount)
{
    if((row < 0) || (row >= rowCount) || (col < 0) || (col >= COLS) || (map[row][col] != '*') || (visited[row][col] == 1)) return;

    visited[row][col] = 1;

    //calling neighbours
    markVisted(map, visited, row+1, col, rowCount);
    markVisted(map, visited, row, col+1, rowCount);
    markVisted(map, visited, row-1, col, rowCount);
    markVisted(map, visited, row, col-1, rowCount);
    markVisted(map, visited, row+1, col+1, rowCount);
    markVisted(map, visited, row-1, col-1, rowCount);
    markVisted(map, visited, row-1, col+1, rowCount);
    markVisted(map, visited, row+1, col-1, rowCount);
}
int countIslands(char map[][COLS], int visited[][COLS], int rowCount)
{
    int i, j, count = 0;
    for(i=0; i<rowCount; ++i){
        for(j=0; j<COLS; ++j){

            if((map[i][j] == '*') && (visited[i][j] == 0)){
                ++count;
                markVisted(map, visited, i, j, rowCount);
            }
        }
    }
    return count;
}

int main()
{
    char map[][COLS] = {
                    "*..........",
                    "**........*",
                    "...........",
                    "...*.......",
                    "*........*.",
                    "..........*"               
                    };
    int rows = sizeof(map)/sizeof(map[0]);
    int visited[rows][COLS], i, j;  

    for(i=0; i<rows; ++i){
        for(j=0; j<COLS; ++j) visited[i][j] = 0;
    }

    printf("No. of islands = %dn", countIslands(map, visited, rows));


    return 0;
}

请提出一些更好的逻辑，对于这个问题 同时，建议，以改善我的解决方案是值得欢迎的。

please suggest some better logic for this problem also, suggestions to improve my solution is welcomed.

推荐答案

我觉得这里的混乱是你的算法并真正以线性时间运行，而不是二次的时间。

I think the confusion here is that your algorithm does actually run in linear time, not quadratic time.

在使用大O表示法， N 为输入的内容。在这里你输入的没有的只是研究或只是 C ，而是研究 * C ，因为它是节点的网格。你的算法 O（R * C），你在你的问题说......因此你的算法运行为O（n）这是线性时间。

......
.****.
.****.
.****.
.****.
......

......
.*.*..
..*.*.
.*.*..
..*.*.
......