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; }
Sunday, 23 October 2016
Connected Cell in a Grid (CTCI)
Problem: Connected Cell in a Grid
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment