题目3 : Counting Islands II 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Country H is going to carry out a huge artificial islands project. The project region is divided into a 1000x1000 grid. The whole project will last for N weeks. Each week one unit area of sea will be filled with land. As a result, new islands (an island consists of all connected land in 4 -- up, down, left and right -- directions) emerges in this region. Suppose the coordinates of the filled units are (0, 0), (1, 1), (1, 0). Then after the first week there is one island: #... .... .... .... After the second week there are two islands: #... .#.. .... .... After the three week the two previous islands are connected by the newly filled land and thus merge into one bigger island: #... ##.. .... .... Your task is track the number of islands after each week's land filling. 输入 The first line contains an integer N denoting the number of weeks. (1 ≤ N ≤ 100000) Each of the following N lines contains two integer x and y denoting the coordinates of the filled area. (0 ≤ x, y < 1000) 输出 For each week output the number of islands after that week's land filling. 样例输入 3 0 0 1 1 1 0 样例输出 1 2 1
四路：这个是一个并查集的题目
代码：
islandSet={}
n=int(raw_input())
num=0
def getRoot(x,y):
parent=islandSet[(x,y)]
if(parent==(x,y)):
return (x,y)
else:
root=getRoot(parent[0],parent[1])
islandSet[(x,y)]=root
return root
def test(x,y,nx,ny):
global num
if islandSet.has_key((x,y)):
root = getRoot(x,y)
if(root!=(nx,ny)):
islandSet[root]=(nx,ny)
num-=1
def addPoint(x,y):
global num
islandSet[(x,y)]=(x,y)
num=num+1
if x>0:test(x-1,y,x,y)
if(y>0):test(x,y-1,x,y)
if(x<999):test(x+1,y,x,y)
if(y<999):test(x,y+1,x,y)
for i in range(0,n):
line =raw_input().split(" ")
x=int(line[0])
y=int(line[1])
addPoint(x,y)
print(num)
代码地址：
https://github.com/iptop/hihoCoderProblemSolving/blob/master/Counting%20Islands%20II/main.py#L1