可以计算位图中的连续区域是否可以改善O(r*c)？

Question

您将获得由卫星拍摄的表面图像.图像是位图,其中水被标记为'.' 和土地用' *' 标记.相邻的群体*形成一个岛屿.(*如果它们是水平,垂直或对角线的邻居,则两个' 相邻).您的任务是打印位图中的岛数.

示例输入: -

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

输出: - 5

在这里,我的实现是占用O(r * c)空间和O(r * c)空间,其中r是总数.行和c是col的总数.

#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 = %d\n", countIslands(map, visited, rows));


    return 0;
}

请为此问题提出一些更好的逻辑,
欢迎提出改进我的解决方案的建议.

Answer 1

我认为这里的混乱是你的算法确实在线性时间内运行,而不是二次时间.

使用big-O表示法时,n代表输入大小.在这里您输入的不只是r或只是c,而是r*c,因为它是节点的网格.你的算法在运行O(r * c),当你在你的问题说......这样你的算法运行中O(n)是线性时间.

在我看来,解决这个问题的任何算法都必须在最坏的情况下读取每个输入单元一次.因此,您可以期待的最佳运行时间是O(n).当您的算法运行时O(n),在最坏的情况下,您不能使用任何运行更快顺序的算法,而不是您提出的算法.

我可以想到一些聪明的技巧.例如,如果你有一块*s,在某些情况下你只能检查对角线.也就是说,如果你有

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

如果你只读这些细胞就没关系了:

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

除非您在最左下角有一些东西,在这种情况下,您需要阅读最左下角的内容*.因此,在某些情况下,您的算法可以更快地运行,但对于最坏的情况(这是什么O度量),它必须是O(n).

编辑:即使在你只读取一半节点的情况下,运行时O(n/2)仍然是相同的顺序(O(n)).