Pythonでグリッドにブロックを1つずつ追加して島の数を見つけるプログラム

水のグリッドが1つあるとします。そのグリッドに土地のブロックを1つずつ追加できます。 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] as

これを解決するには、次の手順に従います-

• d：=[（-1、0）、（0、1）、（1、0）、（0、-1）]

  のような方向のリスト

• idx：=0

• mp：=新しいマップ

• p：=新しいリスト

• サイズ：=新しいリスト

• 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

  • サイズ[pv]：=サイズ[pv]+サイズ[pu]

• メインの方法から、次のようにします-

• land_requestsのリクエストごとに、実行します

  • （i、j）：=リクエスト

  • mp [i、j]：=idx

  • pの最後にidxを挿入します

  • サイズの最後に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を挿入します

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

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))

入力

[[1, 1],[2, 4],[1, 2],[1, 4],[1, 3]]

出力

[1, 2, 2, 2, 1]