hihoCoder 1487-岛屿3

---

有一个1000*1000的海域，每周往其中填入1*1的陆地，要求输出每周该海域中会形成多少个岛屿，以及岛屿的总面积和总周长。 其实这题不算难，只是太久没用并查集，用了DFS导致超时了。现在分别介绍两种方法。 首先我们来解决总面积和总周长这两个问题。 总面积好说，每周填入一个单元的陆地，则面积加一。 总周长要稍微注意，如果新加入的方块和其他所有方块都不邻接，则贡献+4周长；如果和一个已有方块邻接，则贡献+4-2周长；如果和两个已有方块邻接，则贡献+4-2*2周长；如果和3个已有方块邻接，则贡献+4-2*3周长。。。所以每加入一个方块，就看看该方块四周，如果和intercnt个方块邻接，则贡献周长+4-2*intercnt。 最麻烦的是求岛屿个数。当然可以像往常一样，对所有点DFS，求连通分量，但是TLE。 我稍微优化了一下，在board中，把每个连通分量都标记为一个不同的islandID，每次新加入一个方块时，令board[x][y]=++islandID，并从这个方块开始DFS，把所有和(x,y)连通的方块的ID都标记为新的(x,y)的islandID，同时记录一下被(x,y) DFS的方块旧的islandID。通过这个过程，能知道新方块(x,y)和多少个不同的旧岛屿相连，同时把所有和(x,y)相连的旧岛屿都标记为新的islandID了。 假设原来有n个岛屿，和新方块相连的旧岛屿有m个，则加入新方块之后，岛屿数更新为n-m+1，即m个旧岛屿都缩成1个新岛屿了。 DFS思路的代码如下： [cpp] #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; } [/cpp] 本代码提交TLE，用时2792MS。 比赛结束之后，看了看AC的代码，用的全是并查集，没一个用DFS的。。。 好吧，那就改成并查集。求总面积和总周长的方法都一样，不同的是求岛屿个数。 我们用数组来实现并查集，把坐标(x,y)编码成x*1000+y便于存入一维数组。对于每个新加入的点u，在并查集中先用自己代表自己，represent[u]=u。然后环顾四周，把四周陆地所在岛屿的代表放到neighbor中并去重，这样就能得到新方块邻接的旧岛屿数，根据n-m+1算到新岛屿数。最后把邻接的旧岛屿和新方块u union起来。 代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时436MS，果然快了不少。]]>