1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
|
#include <iostream> #include <cmath> using namespace std; const int maxn = 100, n = 3, m = 5; int pre[n * m]; int dir[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int maps[3][5] = { 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, }; struct Node { int x, y; } Point[n * m];
int find(int x) { return x == pre[x] ? x : pre[x] = find(pre[x]); }
void Union(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) { pre[fx] = fy; } }
int main() { int len = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (maps[i][j] == 0) { Point[len++] = Node{i, j}; } } } for (int i = 0; i < len; i++) { pre[i] = i; } for (int i = 0; i < len; i++) { int x = Point[i].x, y = Point[i].y; for (int j = i + 1; j < len; j++) { int nx = Point[j].x, ny = Point[j].y; if (abs(x - nx) + abs(y - ny) == 1) { Union(i, j); } } } int cnt = 0; for (int i = 0; i < len; i++) { if (i == find(i)) cnt++; } for (int i = 0; i < len; i++) cout << pre[i] << " "; cout << endl; cout << cnt << endl; }
|