你会得到一张由卫星拍摄的表面图像。该图像是一个位图，其中水用"."标记，土地用"*"标记。相邻的*群形成一个岛屿。（如果两个'*'是水平、垂直或对角线相邻的）。您的任务是打印位图中的岛屿数。
示例输入：-
.........**
**......***
...........
...*.......
*........*.
*.........*
输出：- 5
在这里，是我的实现，它占用了O(r * c)空间和O(r * c)空间，其中 are 是完全没有的行数，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 = %dn", countIslands(map, visited, rows));
return 0;
}
请为这个问题
提出一些更好的逻辑此外，欢迎提出改进我的解决方案的建议。
我认为这里的困惑在于您的算法实际上是在线性时间而不是二次时间中运行的。
使用 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)）。
这与连接的组件标签高度相关。连接组件的数量只是标签的副产品。链接的维基百科文章中描述的算法以线性时间工作。
-
创建一个无向图，其中每个岛节点都连接到其邻域岛节点。
-
虽然有未访问的节点：
- 选择一个未访问的节点，执行深度优先遍历并标记每个访问过的节点，增加number_of_islands。
-
做。
（1） 和 （2） 都需要 O（n） 时间。
近地，你的方法是最好的O（n）。
但是，我注意到了几件事：
第一：
在函数标记内访问了，您按顺序检查单元格邻居：
down, right, up, left, down-right, up-left, up-right, down-left
更好的顺序是：
left, right, up-left, up, up-right, down-left, down, down-right
这将在缓存中发挥更好的作用，因为它是通过直接读取当前位置旁边的值开始的，并在给定的行中按顺序读取。
（请注意，从对角线开始会将访问标记到更多位置，但由于检查是否访问了单元格只是最后一次检查，因此不会节省任何时间）。
其次：
在仅包含陆地的卫星图像的最坏情况下，您的算法将多次访问每个像元（类似于小区拥有的每个邻居一次）。
这意味着您执行的阵列访问大约是所需数量的八倍。
我相信你可以通过或多或少地线性传递数据来解决这个问题。
我目前正在考虑一种方法，如果它有效，我将添加代码作为编辑。
如果对孤岛的性质没有任何先验知识，算法就不可能在时间上比 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: %dn", main_count);
return 0;
}