Created
April 17, 2016 03:08
-
-
Save jianminchen/a43da87aff353d894a22453668a962d2 to your computer and use it in GitHub Desktop.
C++ - use make_pair, queue, and array size of 16, use queue - BFS - not DFS
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 <cstdio> | |
#include <queue> | |
#include <utility> | |
using namespace std; | |
int m, n; | |
int grid[16][16]; | |
bool vis[16][16]; | |
int bfs(int a, int b) { | |
queue<pair<int, int> > q; | |
q.push(make_pair(a, b)); | |
int k = 0; | |
while (!q.empty()) { | |
pair<int, int> cur = q.front(); | |
q.pop(); | |
if (vis[cur.first][cur.second]) { | |
continue; | |
} | |
vis[cur.first][cur.second] = true; | |
k++; | |
for (int di = -1; di <= 1; di++) { | |
for (int dj = -1; dj <= 1; dj++) { | |
int ci = cur.first + di; | |
int cj = cur.second + dj; | |
if (ci >= 0 && ci < m && cj >= 0 && cj < n && grid[ci][cj] && !vis[ci][cj]) { | |
q.push(make_pair(ci, cj)); | |
} | |
} | |
} | |
} | |
return k; | |
} | |
int main() { | |
scanf("%d %d", &m, &n); | |
for (int i = 0; i < m; i++) { | |
for (int j = 0; j < n; j++) { | |
scanf("%d", &grid[i][j]); | |
} | |
} | |
int ans = 0; | |
for (int i = 0; i < m; i++) { | |
for (int j = 0; j < n; j++) { | |
if (grid[i][j] && !vis[i][j]) { | |
ans = max(ans, bfs(i, j)); | |
} | |
} | |
} | |
printf("%d\n", ans); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment