我要招人

去企业版

首页 > 试题广场 >

几个岛

[编程题]几个岛

热度指数：3879 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个m行n列的二维地图, 初始化每个单元都是水.

操作addLand 把单元格(row,col)变成陆地.

岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).

在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.

二维地图的每条边界外侧假定都是水.

输入描述:

多组测试数据，请参考例题处理 每组数据k+3行, k表示addLand操作次数 第一行:表示行数m 第二行:表示列数n 第三行:表示addLand操作次数k 第4~k+3行:row col 表示addLand的坐标。注意超过边界的坐标是无效的。

输出描述:

一行,k个整数, 表示每次addLand操作后岛屿的个数, 用空格隔开，结尾无空格

示例1

输入

输出

1 1 2 3

算法知识视频讲解

Python

落日有星

思路是：

1. 判断是否越界

2. 判断每次addLand操作，是否与之前的land存在同行或同列

2.1 如果同行或同列，判断另外一个坐标是否相邻（差值的绝对值小于1）

3. 否则增加一个岛屿

python代码如下：

n = eval(input())
m = eval(input())
k = eval(input())
row_,col_,count_ = [],[],[]
count = 0


def find_all_index(arr, item):
    return [i for i, a in enumerate(arr) if a == item]

for i in range(k):
    row,col = list(map(int,input().split(' ')))
    if row>n or col>m:
        print("坐标无效请重新输入。")
        i=i-1
    elif row in row_:
        temp_ = find_all_index(row_,row)
        for item in temp_:
            if abs(col_[item]-col)<=1:
                row_.append(row)
                col_.append(col)
                count_.append(count)   
            else:
                row_.append(row)
                col_.append(col)
                count = count + 1
                count_.append(count)     
    elif col in col_:
        temp_ = find_all_index(col_,col)
        for item in temp_:
            if abs(row_[item]-row)<=1:
                row_.append(row)
                col_.append(col)     
                count_.append(count)
            else:
                row_.append(row)
                col_.append(col)
                count = count + 1
                count_.append(count)
    else:
        row_.append(row)
        col_.append(col)
        count = count + 1
        count_.append(count)
for item in count_:
    print(item,end=' ')

0 0 到 0 5 为什么会是相邻的岛屿？

发表于 2019-10-18 11:28:15 回复(2)

Python

MeredithChai

核心思想只有一句（注释那行）：

新的岛屿数目 = 原有岛屿数目 + 1 - 现添加位置的联通桥数目

这里的联通桥，指该点与原集合中存在相邻上下左右点(岛)的数目

#islandNum = islandNum+1-countBridge !!!
row,col,optNum = int(input()),int(input()),int(input())
land,islandNum,island = [],0,''
for i in range(optNum):
    addLand = list(map(int,input().split()))
    if addLand[0]>row-1 or \
        addLand[1]<col-1:
        pass
    else:
        loc = (addLand[0],addLand[1])
        bridgeNum = 0
        if loc not in land:
            bridgeNum += int((loc[0]-1,loc[1]) in land)+ \
                 int((loc[0]+1,loc[1]) in land)+ \
                 int((loc[0],loc[1]-1) in land)+ \
                 int((loc[0],loc[1]+1) in land)            
            land.append(loc)
            islandNum += 1-bridgeNum
        if islandNum==0: islandNum = 1
    island += str(islandNum)+' '
print(island[:-1])

############################## 我是分割线 ##############################

19-09-10: 感谢评论的提醒！原提交的代码直接复制进来没注意格式（这里头的代码排版还需要切回html, emmmmm），下面是提交时的代码：

编辑于 2019-09-10 10:12:30 回复(4)

Python

华科平凡

python解法

经典的岛屿问题，又掏出了我的祖传代码。
不过题目有坑：

要判断行数与列数有没有越界。
还有越界后的处理，发现测试用例中对于越界还是取上一次的结果，这个使用数组记录上一次操作后岛屿的数量即可。
一开始要在res数组里做一个初始化值0，防止一上来就越界，此时岛屿数量为0。

代码如下：

import copy


class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid: return 0
        row, col = len(grid), len(grid[0])
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    res += 1
                    self.merge(grid, i, j)

        return res

    def merge(self, grid, i, j):
        row = len(grid)
        col = len(grid[0])

        if i < 0 or i >= row or j < 0 or j >= col or grid[i][j] != "1":  # 退出dfs的条件：1.越界；2.遇到值为0或者已访问的节点(X)
            return

        grid[i][j] = "X"  # 置为"X", 表示该元素已被访问。
        """向四个方向查找"""
        self.merge(grid, i - 1, j)
        self.merge(grid, i + 1, j)
        self.merge(grid, i, j - 1)
        self.merge(grid, i, j + 1)


m, n, k = [int(input()) for _ in range(3)]
land, grid = [["0" for i in range(n)] for j in range(m)], []
solution = Solution()
res = [0]
for i in range(k):
    row, col = map(int, input().split())
    if row < m and col < n:
        land[row][col] = "1"
        grid = copy.deepcopy(land)
        res.append(str(solution.numIslands(grid)))
    else:
        res.append(res[-1])
print(" ".join(res[1:]))

发表于 2019-03-20 22:11:22 回复(0)

Python

晨星201712070130675

问题解决思路的核心就一句话：

numOfIsland=numOfIsland+1-countBridge(row,col)

加入一个岛后岛的数目等于原来岛数目加1减去这个岛带来的桥的数目（该岛与其他岛相连称为有1个桥）

import sys

m=int(sys.stdin.readline().strip())
n=int(sys.stdin.readline().strip())
k=int(sys.stdin.readline().strip())
arr=[[0 for i in range(n)]for i in range(m)]

def inArray(r,c):
if r<0 or r==m or c<0 or c==n:
return 0
return arr[r][c]

def countBridge(row,col):
return inArray(row-1,col)+inArray(row+1,col)+inArray(row,col-1)+inArray(row,col+1)

def addLand(row,col,numOfIsland):
arr[row][col]=1
numOfIsland=numOfIsland+1-countBridge(row,col)
if numOfIsland==0:
numOfIsland=1
sys.stdout.write(str(numOfIsland)+' ')
return numOfIsland

numOfIsland=0
while True:
line= sys.stdin.readline().strip()
if len(line)==0:break
[row,col]=map(int,line.split())
if row<0 or row>m-1 or col<0 or col >n-1:
sys.stdout.write(str(numOfIsland)+' ')
continue
if arr[row][col]==1:
sys.stdout.write(str(numOfIsland)+' ')
else:

numOfIsland=addLand(row,col,numOfIsland)

发表于 2018-10-09 12:48:50 回复(1)

Python

ludihu

m=input() m=int(m) m=m+2 n=input() n=int(n) n=n+2 k=input() k=int(k) list1=[] for i in range(k): j=input().split() list1.append([int(j[0])+1,int(j[1])+1]) list1 list2=[] for i in range(m): list2.append([]) for j in range(n): list2[i].append(0) a=1 for i in range(k): b=0 if i ==0 : print(1) else: for j in range(i): if (list1[j][0]-list1[i][0])**2+(list1[j][1]-list1[i][1])**2<2: b=b+1 if b==0: a=a+1 elif b==1: a=a elif b==2: a=a-1 elif b==3: a=a-2 elif b==4: a=a-3 print(a)

发表于 2018-08-27 16:32:30 回复(0)