在Python中，通过将块添加到网格中来逐个查找岛屿数量的程序

假设我们有一个无限水网格。我们可以逐个向该网格添加土地块。我们有一个名为land_requests的坐标列表，其中每个坐标的形式为[r，c]，其中r表示行，c表示列。我们要找到一个列表，其中每个元素表示从land_requests中添加每个土地块后存在的岛屿数量。

因此，如果输入为land_requests = [[1, 1]，[2, 4]，[1, 2]，[1, 4]，[1, 3]]，则输出将是[1，2，2，2，1]，如下所示：

针对此问题，我们将遵循以下步骤-

d：一个方向列表，例如[（-1,0），（0,1），（1,0），（0，-1）]
idx：0
mp：一个新地图
p：一个新列表
size：一个新列表
comp：0
ans：一个新列表
定义一个名为search()的函数。这将以u为参数
如果u与p [u]相同，则
- 返回u
- p [u]：= search（p [u]）
返回p [u]
定义一个名为connect()的函数。这将以u，v为参数
pu：= search（u），pv：= search（v）
如果pu等于pv，则
- 返回
comp：= comp-1
如果size [pu]> = size [pv]，则
- p [pv]：= pu
- size [pu]：= size [pu] + size [pv]
否则，
- p [pu]：= pv
- size [pv]：= size [pv] + size [pu]
在主方法中执行以下操作-
对于land_requests中的每个请求，请执行以下操作
- （i，j）：=请求
- mp [i，j]：= idx
- 在p的末尾插入idx
- 在size的末尾插入1
- idx：= idx + 1
- comp：= comp + 1
- 对于d中的每个k，请执行以下操作
  - ni：= i + k [1]
  - nj：= j + k [0]
  - 如果（ni，nj）在mp中，则
  - connect（mp [（i，j）]，mp [（ni，nj）]）
- 在ans的末尾插入comp
返回答案

让我们看下面的实现以更好地理解-

示例

d = [(−1, 0), (0, 1), (1, 0), (0, −1)]
class Solution:
    def search(self, u):
        if u == self.p[u]:
            return u
        self.p[u] = self.search(self.p[u])
        return self.p[u]
    def connect(self, u, v):
        pu = self.search(u)
        pv = self.search(v)
        if pu == pv:
            return
        self.comp −= 1
        if self.size[pu] >= self.size[pv]:
            self.p[pv] = pu
            self.size[pu] += self.size[pv]
        else:
            self.p[pu] = pv
            self.size[pv] += self.size[pu]
    def solve(self, land_requests):
        self.idx = 0
        self.mp = dict()
        self.p = []
        self.size = []
        self.comp = 0
        ans = []
        for request in land_requests:
            i, j = request
            self.mp[(i, j)] = self.idx
            self.p.append(self.idx)
            self.size.append(1)
            self.idx += 1
            self.comp += 1
            for k in d:
                ni = i + k[1]
                nj = j + k[0]
                if (ni, nj) in self.mp:
                    self.connect(self.mp[(i, j)], self.mp[(ni, nj)])
            ans.append(self.comp)
        return ans
ob = Solution()
land_requests = [[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]
print(ob.solve(land_requests))