Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 17, 2016 03:18
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/3e489592beaa267c10540302bf08745b to your computer and use it in GitHub Desktop.
Save jianminchen/3e489592beaa267c10540302bf08745b to your computer and use it in GitHub Desktop.
C++ solution - use vector to express two dimensional array, and then, define two vectors for neighbors - 8 neighbors, two queues.
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int M, N;
cin >> M >> N;
vector<int> grow(N+2,0);
vector<vector<int> > grid(M+2, grow);
for(int y=1;y<=M;y++){
for(int x=1;x<=N;x++){
cin >> grid[y][x];
}
}
vector<int> dx = {1, 1, 0, -1, -1, -1, 0, 1};
vector<int> dy = {0, 1, 1, 1, 0, -1, -1, -1};
int best_comp = 0;
for(int y=1;y<=M;y++){
for(int x=1;x<=N;x++){
if(grid[y][x]==1){
int cur_comp = 0;
queue<int> bfsx;
queue<int> bfsy;
bfsx.push(x);
bfsy.push(y);
grid[y][x] = 0;
while(!bfsx.empty()){
cur_comp++;
int curx = bfsx.front();
int cury = bfsy.front();
bfsx.pop(); bfsy.pop();
for(int i=0;i<8;i++){
int nextx = curx+dx[i];
int nexty = cury+dy[i];
if(grid[nexty][nextx]==1){
bfsx.push(nextx);
bfsy.push(nexty);
grid[nexty][nextx]=0;
}
}
}
if(cur_comp > best_comp) best_comp = cur_comp;
}
}
}
cout << best_comp << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment