首页 > 代码库 > hihocoder offer收割编程练习赛11 C 岛屿3
hihocoder offer收割编程练习赛11 C 岛屿3
思路:
并查集的应用。
实现:
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 bool a[1005][1005]; 6 int n, x, y; 7 int par[1000005]; 8 int ran[1000005]; 9 int dx[4] = { 1, 0, -1, 0 }; 10 int dy[4] = { 0, 1, 0, -1 }; 11 12 void init(int n) 13 { 14 for (int i = 0; i < n; i++) 15 { 16 ran[i] = 0; 17 par[i] = i; 18 } 19 } 20 21 int find(int x) 22 { 23 if (par[x] == x) 24 return x; 25 return par[x] = find(par[x]); 26 } 27 28 29 void unite(int x, int y) 30 { 31 x = find(x); 32 y = find(y); 33 if (x == y) 34 return; 35 if (ran[x] < ran[y]) 36 par[x] = y; 37 else 38 { 39 par[y] = x; 40 if (ran[x] == ran[y]) 41 ran[x]++; 42 } 43 } 44 45 bool same(int x, int y) 46 { 47 return find(x) == find(y); 48 } 49 50 int trans(int x, int y) 51 { 52 return x * 1000 + y; 53 } 54 55 int main() 56 { 57 init(1000005); 58 cin >> n; 59 int now = 0, c = 0; 60 for (int i = 0; i < n; i++) 61 { 62 now++; 63 c += 4; 64 cin >> x >> y; 65 a[x][y] = true; 66 int tmp = trans(x, y); 67 for (int j = 0; j < 4; j++) 68 { 69 int nx = x + dx[j]; 70 int ny = y + dy[j]; 71 if (nx >= 0 && nx < 1000 && ny >= 0 && ny < 1000 && a[nx][ny]) 72 { 73 int t = trans(nx, ny); 74 if (!same(tmp, t)) 75 { 76 unite(tmp, t); 77 now--; 78 } 79 c -= 2; 80 } 81 } 82 cout << now << " " << i + 1 << " " << c << endl; 83 } 84 return 0; 85 }
hihocoder offer收割编程练习赛11 C 岛屿3
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。