8

给您一张由卫星拍摄的表面图像。该图像是一个位图，其中水标有“。” 土地用“ *”标记。相邻的 ' 组*形成一个岛。（如果两个 ' *' 是水平、垂直或对角相邻的，则它们是相邻的）。您的任务是打印位图中的岛屿数量。

示例输入：-

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

输出：- 5

这是我的实现，它占用O(r * c)空间和O(r * c)空间，其中 r 是总数。行数，c 是列数。

#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;
}

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

4

5 回答 5

9

我认为这里的困惑在于您的算法实际上确实以线性时间运行，而不是二次时间。

使用大 O 表示法时，n代表输入大小。您在此处的输入不仅仅是，r而是c* r，c因为它是一个节点网格。正如您在问题中所说，您的算法运行O(r * c)在...因此您的算法运行O(n)在线性时间。

在我看来，任何解决这个问题的算法都必须在最坏的情况下读取每个输入单元格一次。因此，您可以期望的最佳运行时间是O(n). 当您的算法运行时O(n)，在最坏的情况下，您无法拥有比您提出的算法运行速度更快的任何算法。

我能想到一些巧妙的技巧。例如，如果你有一个*s 块，在某些情况下你只能检查对角线。也就是说，如果你有

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

如果您只阅读这些单元格，则无关紧要：

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

除非例如您在最左下角有东西，在这种情况下，您需要阅读最左下角的内容*。所以也许在某些情况下你的算法可以运行得更快，但对于最坏的情况（这是什么O措施），它必须是O(n).

编辑：即使在您只读取一半节点的情况下，运行时间O(n/2)仍然是相同的顺序（O(n)）。

于 2012-08-13T14:34:10.980 回答
2

这与连接组件标记高度相关。连接组件的数量只是标签的副产品。链接的维基百科文章中描述的算法在线性时间内工作。

于 2012-08-13T14:23:50.577 回答
1

  1. 创建一个无向图，其中每个岛节点都连接到其相邻的岛节点。

  2. 虽然有未访问的节点：

    • 选择一个未访问的节点，进行深度优先遍历并标记每个访问过的节点，增加 number_of_islands。

  3. 完毕。

(1) 和 (2) 都需要 O(n) 时间。

于 2012-08-13T14:24:59.407 回答
1

渐近地，您的方法是最好的 O(n)。

但是，我注意到了几件事：

第一的：

在函数 markVisited 中，您按顺序检查单元格邻居：

down, right, up, left, down-right, up-left, up-right, down-left

更好的顺序是：

left, right, up-left, up, up-right, down-left, down, down-right

这将在缓存中更好地发挥作用，因为它是通过直接读取当前位置旁边的值开始的，并且在给定的行中按顺序读取。

（请注意，从对角线开始会标记访问过更多的位置，但由于检查是否访问过一个单元格只是最后一次检查，因此不会节省任何时间）。

第二：

在仅包含陆地的卫星图像的最坏情况下，您的算法将多次访问每个单元格（类似于单元格拥有的每个邻居一次）。

这意味着您执行的数组访问次数大约是可能需要的八倍。

我相信您可以通过或多或少地线性传递数据来解决这个问题。

我目前正在考虑一种方法，如果可行，我会将代码添加为编辑。

于 2012-08-14T21:10:50.180 回答
0

如果没有任何关于岛屿性质的先验知识，算法就不能及时比 O(n) 更有效，但是在内存方面可以改进你的算法。访问的数组只是多余的。这是一个快速尝试（请原谅使用 ASCII 算法 - 不那么可读，但编码速度更快）

#include <stdio.h>
#define COLS 12


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

    int main_count = 0;

    if(map[0][0] == '*') {
        main_count++;
    }
    for(j=0; j<COLS-1; j++) {
        if((map[0][j]-map[0][j+1])==4) {
            main_count++;   
        }
    }

    for(i=1; i<rows; ++i){
        if(map[i][0] == '*' && (map[i][0]-map[i-1][0]-map[i-1][1])==-50) {
            main_count++;
        }
        for(j=0; j<COLS-1; j++) {
            if((map[i][j]-map[i][j+1])==4) {
                if( j==COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])==-50) {
                    main_count++;
                }   
                if( j!=COLS-2 && (map[i][j+1]-map[i-1][j]-map[i-1][j+1])-map[i-1][j+1]==-96) {
                    main_count++;
                }   
            }
        }
    }

    printf("Number of islands: %d\n", main_count);

    return 0;
}
于 2012-08-13T20:50:19.080 回答