Sunday 23 October 2016

Connected Cell in a Grid (CTCI)

Problem: Connected Cell in a Grid

int n, m;
bool vis[10][10];

void dfs(vector< vector<int> > grid, int row, int col, int *cnt)
{
    vis[row][col]=1;
    *cnt = *cnt + 1;
    for(int i=-1;i<=1;i++)
        for(int j=-1;j<=1;j++)
        {
            if(!i && !j) continue;
            if(row+i>=0 && row+i<n && col+j>=0 && col+j<m)
                if(!vis[row+i][col+j])
                    if(grid[row+i][col+j]==1)
                        dfs(grid, row+i, col+j, cnt);
        }
   return;
}

int get_biggest_region(vector< vector<int> > grid) {
    int row = grid.size(), col = grid[0].size(), mx=0, tmp;
    memset(vis, 0, sizeof(vis));
    for(int i=0;i<row;i++)
        for(int j=0;j<col;j++)
            if(!vis[i][j] && grid[i][j])
            {
                tmp=0;
                dfs(grid, i, j, &tmp);
                mx = max(mx, tmp);
            }
     return mx;
}

int main(){
    cin >> n;
    cin >> m;
    vector< vector<int> > grid(n,vector<int>(m));
    for(int grid_i = 0;grid_i < n;grid_i++){
       for(int grid_j = 0;grid_j < m;grid_j++){
          cin >> grid[grid_i][grid_j];
       }
    }
    cout << get_biggest_region(grid) << endl;
    return 0;
}

No comments:

Post a Comment