hihoCoder 1487-岛屿3

hihoCoder 1487-岛屿3

#1487 : 岛屿3

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

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

每周都有一块1x1的单位方格海域被填成陆地。如果我们将连成一片的陆地(一块单位方格与它上下左右4个单位方格是相连的)视为岛屿,H国想监测每周末整片海域中一共存在有多少个岛屿,以及这些岛屿的总面积和总周长各是多少。

假设工程持续三周,第一周被填的海域坐标是(0, 0),那么第一周结束后有1座岛屿、总面积是1、总周长是4:

#..
...
...

第二周被填的海域坐标是(1, 1),那么第二周结束后有2座岛屿、总面积是2、总周长是8:

#..
.#.
...

第三周被填的海域坐标是(1, 0),那么第三周结束后有1座岛屿、总面积是3、总周长是8:

#..
##.
...

你能完成这项任务么?

输入

第一行包含一个整数N,表示工程持续的周数。(1 <= N <= 100000)

以下N行每行包含两个整数x和y,表示当周被填的海域坐标。(0 <= x, y < 1000)

输出

输出N行,每行包含3个整数,依次是当周末岛屿的数量、总面积和总周长。

样例输入
3  
0 0   
1 1   
1 0
样例输出
1 1 4  
2 2 8  
1 3 8

有一个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思路的代码如下:

#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;
}

本代码提交TLE,用时2792MS。

比赛结束之后,看了看AC的代码,用的全是并查集,没一个用DFS的。。。

好吧,那就改成并查集。求总面积和总周长的方法都一样,不同的是求岛屿个数。

我们用数组来实现并查集,把坐标(x,y)编码成x*1000+y便于存入一维数组。对于每个新加入的点u,在并查集中先用自己代表自己,represent[u]=u。然后环顾四周,把四周陆地所在岛屿的代表放到neighbor中并去重,这样就能得到新方块邻接的旧岛屿数,根据n-m+1算到新岛屿数。最后把邻接的旧岛屿和新方块u union起来。

代码如下:

#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;
}

本代码提交AC,用时436MS,果然快了不少。

One thought on “hihoCoder 1487-岛屿3

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

Leave a Reply

Your email address will not be published. Required fields are marked *