Pythonで離れることができない島の数を見つけるためのプログラム

バイナリ行列があるとします。ここで、1は土地を表し、0は水を表します。どの土地からでも、上、下、左、右に移動できますが、別の土地のセルに斜めに移動したり、マトリックスから外れたりすることはできません。マトリックスから外れないランドセルの数を見つける必要があります。

したがって、入力が次のような場合

中央に4つの土地の正方形があり、そこからマトリックスから離れることができないため、出力は4になります。

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

• q：=matrix [i、j]がland iで、jが境界インデックスの場合の各行iと列のペア（i、j）のリスト
• idx：=0
• qの各ペア（x、y）について、
  • matrix [x、y]：=0
• idx
• x、y：=q [idx]
• [（-1、0）、（0、-1）、（0、1）、（1、0）]の各（dx、dy）に対して、do
  • nx：=x + dx
  • ny：=y + dy
  • 0 <=nx <行列の行数、0 <=ny <行列[nx]および行列[nx、ny]の列数が1の場合、
    • matrix [nx、ny]：=0
    • qの最後に（nx、ny）を挿入します
• idx：=idx + 1

例

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

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

入力

[
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]

出力

4