Can count contiguous areas in a bitmap over O (r * c)?

Question

You are presented with an image of a surface photographed by a satellite. The image is a raster image where water is indicated by the letter '.' and the earth is marked ' * '. Adjacent group ' * forms an island. (Two " * " are adjacent if they are horizontal, vertical or diagonal neighbors). Your task is to print the number of islands in the bitmap.

Input Example: -

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

Output: - 5

Here is my implementation that takes the space O(r * c) and O(r * c) , where r is not. rows and c is the total number of col columns.

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

please suggest the best logic for this problem
suggestions for improving my solution are also welcome.

Answer 1

I think the confusion here is that your algorithm really works in linear time, not quadratic time.

When using large output notation, n denotes the size of the input. Your input here is not just r or just c , but rather r * c , since this is a grid of nodes. Your algorithm works in O(r * c) , as you said in your question ... so your algorithm works in O(n) , which is linear time.

It seems to me that any algorithm that solves this problem will have to read each input cell once in the worst case. So the best time you can hope for is O(n) . Since your algorithm runs in O(n) , you cannot have an algorithm that runs faster, in the worst case, than the algorithm you proposed.

I can come up with some clever tricks. For example, if you have a * s block, you can check the diagonals only in certain cases. That is, if you have

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

it doesn't matter if you read only these cells:

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

if, for example, you have something in the lower left corner, in which case you will need to read this very lower left * . So maybe in some cases your algorithm may work faster, but for the worst case (that measures O ) it should be O(n) .

EDIT: even when you read only half the nodes, the runtime will be O(n/2) , which still has the same order ( O(n) ).

Answer 2

This has a lot to do with component binding . The number of connected components is only a byproduct of labeling. The algorithm described in the related wikipedia article works in linear time.

Answer 3

• Create an undirected graph where each island node connects to its neighboring island nodes.

• While there are invisible nodes:

  • select an invisible node, do a depth tour and mark each node visited, increase the number of_definitions.

• Done.

Both (1) and (2) take O (n) time.

Answer 4

Asymptotically, your approach is the best O (n).

However, I noticed a couple of things:

At first:

inside the markVisited function, you check the cell cells in order:

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

Best order:

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

This will play better in the cache, because it starts by reading the values ​​directly next to the current position and sequentially in the given line.

(note that starting from the diagonals, the mark will be visited in more places, but since checking whether a cell was visited is only the last check, it will not save any time).

Secondly:

In the worst case, the satellite image containing only the earth, your algorithm will visit each cell several times (something like one for each neighbor that the cell has).

This means that you are approximately making eight times more access to the array than is possible.

I believe that you can solve this problem by using more or less linear data flow.

I am now thinking of an approach, if it works, I will add the code as an edit.

Answer 5

Without any a priori knowledge of the nature of the islands, the algorithm could not be more efficient than O (n) in time, however, from the point of view of memory, your algorithm can be improved. The visited array is simply redundant. Here's a quick try (to forgive using AHSII artihmetics - not as readable, but faster than code)

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