Want to find Maximum size of an island

Question

#include <bits/stdc++.h> 
using namespace std; 
int ROW,COL;
int isSafe(vector<vector<int>>&M, int row, int col, 
          vector<vector<bool>>&visited) 
{ 
   return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]); 
}
int DFS(vector<vector<int>>&M, int row, int col, 
       vector<vector<bool>>&visited ) 
{ 
   int count= 1;
   
   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; 
 
   // Recur for all connected neighbours 
   for (int k = 0; k < 8; ++k) 
       if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)){ 
           count++;
           DFS(M, row + rowNbr[k], col + colNbr[k], visited); 
       }
       return count;
}
int main() 
{ 
   int t;
   cin>>t;
   for(int i=0;i<t;i++){
       int n,m;
       int max = 0;
       cin>>n>>m;
       ROW=n;
       COL=m;
       vector<vector<int>>g(n,vector<int>(m));
        vector<vector<bool>>visited(n,vector<bool>(m));
       for(int i=0;i<n;i++){
           for (int j=0;j<m;j++){
               cin>>g[i][j];
               visited[i][j]=false;
           }
       }

       for(int i = 0; i < n; i ++)
   {
       for(int j = 0; j < m; j++)
       {
           if(!visited[i][j] && g[i][j] == 1)
           {
               
               int c = DFS(g,i,j,visited);
               if(c > max)
               {
                   max = c;
               }
           }
       }
   }
   cout<<max;
   }
}

I didn't know where I am messing this up. Please Help. Using Here Dfs, to travel adjacent 1's. We know that there can be at max 8 neighbors having 1. So Dfs for 8 times. Here I want to count the maximum number of adjacent 1`s in a given 2d vector. I am unable to figure out where I m getting it wrong. Any help will be appreciated.

Stepping through your program with a debugger should help to identify the problem. — Evg, Jul 04 '20 at 12:50
I haven't looked into the details of your code but you might want to read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Please consider editing your code and your question accordingly. — Martin Konrad, Jul 04 '20 at 12:54

score 2 · Accepted Answer · answered Jul 04 '20 at 12:47

2

The part

           count++;
           DFS(M, row + rowNbr[k], col + colNbr[k], visited);

is ignoring what DFS returned. It should be

           count += DFS(M, row + rowNbr[k], col + colNbr[k], visited);

answered Jul 04 '20 at 12:47

MikeCAT

73,922
11
45
70

Want to find Maximum size of an island

1 Answers1