Created
April 17, 2016 03:18
-
-
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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