title: can counting contiguous regions in a bitmap be improved over O(r * c)?
body: <p>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 '<code>*</code>'. Adjacent group of '<code>*</code>'s form an island. (Two '<code>*</code>' are adjacent if they are horizontal, vertical or diagonal neighbours). Your task is to print the number of islands in the bitmap.</p>
  
  <p>Example Input:-</p>
  
  <pre><code>.........**
  **......***
  ...........
  ...*.......
  *........*.
  *.........*
  </code></pre>
  
  <p>Output:- 5</p>
  
  <p>Here, is my implementation which takes <code>O(r * c)</code> space and <code>O(r * c)</code> space where r is total no. of rows and c is total no of cols.</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #define COLS 12
  
  void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount)
  {
      if((row &lt; 0) || (row &gt;= rowCount) || (col &lt; 0) || (col &gt;= 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&lt;rowCount; ++i){
          for(j=0; j&lt;COLS; ++j){
  
              if((map[i][j] == '*') &amp;&amp; (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&lt;rows; ++i){
          for(j=0; j&lt;COLS; ++j) visited[i][j] = 0;
      }
  
      printf("No. of islands = %d\n", countIslands(map, visited, rows));
  
  
      return 0;
  }
  </code></pre>
  
  <p><strong>please suggest some better logic for this problem</strong><br>
  also, suggestions to improve my solution is welcomed.</p>