title: what can be root cause for this behavior in Optimizing "Number of Islands" program using DFS recursive approach
body: <p>I am having an issue in optimizing the "number of islands" program that I had downloaded from web. I tried optimizing it as explained below, but couldnt get it 100% right. </p>
  
  <p>what is Number of islands ?</p>
  
  <p><a href="http://www.geeksforgeeks.org/find-number-of-islands/" rel="nofollow noreferrer">http://www.geeksforgeeks.org/find-number-of-islands/</a></p>
  
  <p>I have taken the below "c" program from one of the website for determining number of islands in a given graph. </p>
  
  <pre><code>void DFS(int M[][COL], int row, int col, bool visited[][COL])
  {
     // These arrays are used to get row and column numbers of 8 neighbours 
     // of a given cell
     static int rowNbr[] = {-1, -1, -1,  0, 0,  1, 1, 1};
     static int colNbr[] = {-1,  0,  1, -1, 1, -1, 0, 1};
  
     int k = 0;
     // Mark this cell as visited
     visited[row][col] = true;
     printf("\n row=%d, col=%d", row, col); 
  
     // Recur for all connected neighbours
     for (k = 0; k &lt; 8; ++k) {
         printf(" k=%d", k); 
         if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) )
             DFS(M, row + rowNbr[k], col + colNbr[k], visited);
     }
  }
  
  // The main function that returns count of islands in a given boolean
  // 2D matrix
  int countIslands(int M[][COL])
  {
      // Make a bool array to mark visited cells.
      // Initially all cells are unvisited
      bool visited[ROW][COL];
      memset(visited, 0, sizeof(visited));
  
      // Initialize count as 0 and travese through the all cells of
      // given matrix
      int count = 0;
      int i = 0, j=0;
      for (i = 0; i &lt; ROW; ++i) {
          for (j = 0; j &lt; COL; ++j) {
              if (M[i][j] &amp;&amp; !visited[i][j]) // If a cell with value 1 is not
              {                         // visited yet, then new island found
                 DFS(M, i, j, visited);     // Visit all cells in this island.
                 ++count;                   // and increment island count
                 printf("\n count is %d", count);
              }
          }
          printf("\n");
      }
  
      return count;
  }
  
  
  // A function to check if a given cell (row, col) can be included in DFS
  int isSafe(int M[][COL], int row, int col, bool visited[][COL])
  {
      // row number is in range, column number is in range and value is 1 
      // and not yet visited
      printf(" (i=%d, j=%d)", row, col);
      return (row &gt;= 0) &amp;&amp; (row &lt; ROW) &amp;&amp;     
         (col &gt;= 0) &amp;&amp; (col &lt; COL) &amp;&amp;      
         (M[row][col] &amp;&amp; !visited[row][col]); 
  } 
  </code></pre>
  
  <p>As having two for loops for the full matrix size is not the best way of handling this problem, I tried optimizing as below.</p>
  
  <p>In addition to rememeber what node I visited, I also manipulated the indexes "i" and "j" to further optimize and skipping the check for is_visited flag. Hope my explanation is clear. Code below.</p>
  
  <pre><code>// A utility function to do DFS for a 2D boolean matrix. It only considers
  // the 8 neighbours as adjacent vertices
  void DFS_new(int M[][COL], int *row, int *col, bool visited[][COL])
  {
      // These arrays are used to get row and column numbers of 8 neighbours 
      // of a given cell
      int k;
      static int rowNbr[] = {-1, -1, -1,  0, 0,  1, 1, 1};
      static int colNbr[] = {-1,  0,  1, -1, 1, -1, 0, 1};
  
      // Mark this cell as visited
      visited[*row][*col] = true;
      printf("\n row=%d, col=%d", *row, *col); 
      // Recur for all connected neighbours
     for (k = 0; k &lt; 8; ++k) 
     {
         printf(" k=%d", k); 
         if (isSafe(M, (*row) + rowNbr[k], (*col) + colNbr[k], visited) )
         {
             (*row) = (*row)+rowNbr[k];
             (*col) = (*col)+colNbr[k];
             DFS_new(M, row, col, visited);
         }
     }
  }
  
  // The main function that returns count of islands in a given boolean
  // 2D matrix
  int countIslands_new(int M[][COL])
  {
     // Make a bool array to mark visited cells.
     // Initially all cells are unvisited
     bool visited[ROW][COL];
     memset(visited, 0, sizeof(visited)); 
  
      // Initialize count as 0 and travese through the all cells of
     // given matrix
     int count = 0;
     int i = 0, j = 0;
     while (i &lt; ROW) 
     {
         j = 0;
         while (j &lt; COL)
         {
             if (M[i][j] &amp;&amp; !visited[i][j]) 
             {                              
                 DFS_new(M, &amp;i, &amp;j, visited);
                 count++;                    
                printf("\n count is %d", count);
             }
             j++;
         }
         i++;
     } 
     return count;
  }
  </code></pre>
  
  <p>Now coming to the problem, If I use the below input for testing the above two programs, my code gives a wrong output. It indicates the number of islands are 4, where as actually there are only 3 islands. The original program works fine though. </p>
  
  <pre><code>// Driver program to test above function
  int main()
  {
      int M[][COL]= {  {1, 1, 0, 0, 0},
               {0, 1, 0, 1, 0},
               {0, 0, 0, 0, 0},
               {0, 1, 0, 1, 0},
               {1, 0, 1, 0, 1}
            };
  
      printf("Number of islands is: %d\n", countIslands(M));
  
      return 0;
  }   
  </code></pre>
  
  <p>One particular thing that I observed for which I couldn't build the logic is as below.</p>
  
  <p>In my program, I see that below code snippet from my program in function DFS_new is getting executed more than 8 times without this function getting called again (I mean without even recursive function getting called). </p>
  
  <pre><code>for (k = 0; k &lt; 8; ++k) 
  {
      printf(" k=%d", k); 
  }
  </code></pre>
  
  <p>output of the printf below:</p>
  
  <pre><code> row=4, col=0 k=0 (i=3, j=-1) k=1 (i=3, j=0) k=2 (i=3, j=1) k=3 (i=4, j=-1) 
   k=4 (i=4, j=1) k=5 (i=5, j=-1) **k=6** (i=5, j=0) **k=7** (i=5, j=1) 
   **k=6** (i=4, j=1) **k=7** (i=4, j=2)
  </code></pre>
  
  <p>Hope this question makes sense to this forum and expecting a positive response. </p>