# hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

### 描述

H国正在进行一项持续N周的填海造岛工程。整片工程海域可以被看作是1000x1000的网格。

```#..
...
...
```

```#..
.#.
...
```

```#..
##.
...
```

### 输出

```3
0 0
1 1
1 0```

```1 1 4
2 2 8
1 3 8```

DFS思路的代码如下：

```#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int,int>> dirs = { {1,0},{-1,0},{0,1},{0,-1} };
void dfs(int x,int y, int islandID, unordered_set<int>& neighbor) {
neighbor.insert(board[x][y]);
board[x][y] = islandID;
for (int i = 0; i < dirs.size(); ++i) {
int newx = x + dirs[i].first, newy = y + dirs[i].second;
if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0 && board[newx][newy] != islandID)dfs(newx, newy, islandID, neighbor);
}
}
int main() {
//freopen("input.txt", "r", stdin);
int N, x, y;
int island = 0, area = 0, perimeter = 0;
int islandID = 1;
bool first = true;
scanf("%d", &N);
while (N--) {
scanf("%d %d", &x, &y);
board[x][y] = islandID;
++area;
if (first) {
perimeter = 4;
island = 1;
first = false;
}
else {
int intercnt = 0; // 邻接方块数
for (int i = 0; i < dirs.size(); ++i) {
int newx = x + dirs[i].first, newy = y + dirs[i].second;
if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] != 0)++intercnt;
}
perimeter = perimeter + 4 - 2 * intercnt;
if (intercnt == 0)++island;
else {
unordered_set<int> neighbor; // 邻接岛屿旧编号+新方块编号
dfs(x, y, islandID, neighbor);
island = island - neighbor.size() + 2; // 因为neighbor中包含新方块编号，所以这里要多加1
}
}
++islandID;
printf("%d %d %d\n", island, area, perimeter);
}
return 0;
}
```

```#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<unordered_set>
using namespace std;
vector<vector<int>> board(1000, vector<int>(1000, 0));
vector<pair<int, int>> dirs = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
vector<int> represent(1000 * 1000, -1);
int find_rep(int u) {
if (u == represent[u])return u;
else {
represent[u] = find_rep(represent[u]);
return represent[u];
}
}
void union_rep(int u, int v) {
represent[find_rep(u)] = find_rep(v);
}
int main() {
//freopen("input.txt", "r", stdin);
int N, x, y, u;
int island = 0, area = 0, perimeter = 0;
bool first = true;
scanf("%d", &N);
while (N--) {
scanf("%d %d", &x, &y);
board[x][y] = 1;
++area;
u = x * 1000 + y;
represent[u] = u;
if (first) {
perimeter = 4;
island = 1;
first = false;
}
else {
int intercnt = 0; // 邻接方块数
unordered_set<int> neighbor; // 邻接岛屿
for (int i = 0; i < dirs.size(); ++i) {
int newx = x + dirs[i].first, newy = y + dirs[i].second;
if (newx >= 0 && newx < 1000 && newy >= 0 && newy < 1000 && board[newx][newy] == 1) {
++intercnt;
neighbor.insert(find_rep(newx * 1000 + newy));
}
}
for (auto it = neighbor.begin(); it != neighbor.end(); ++it)union_rep(u, *it);
perimeter = perimeter + 4 - 2 * intercnt;
island = island - neighbor.size() + 1;
}
printf("%d %d %d\n", island, area, perimeter);
}
return 0;
}
```

## 1 thought on “hihoCoder 1487-岛屿3”

1. Pingback: hihoCoder 1495-矩形分割 | bitJoy > code

This site uses Akismet to reduce spam. Learn how your comment data is processed.