100. 島の最大面積
与えられた1（陸地）と0（水）からなる行列において、島の最大面積を計算します。島は水平または垂直方向に隣接する陸地で構成され、周囲が水で囲まれているものとします。
from collections import deque
def max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
max_area = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
current_area = 0
queue = deque([(i, j)])
grid[i][j] = 0
while queue:
x, y = queue.popleft()
current_area += 1
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
nx, ny = x+dx, y+dy
if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]==1:
grid[nx][ny] = 0
queue.append((nx, ny))
max_area = max(max_area, current_area)
return max_area
</code>101. 孤立島の総面積
行列の端に接していない島（孤立島）の総面積を計算します。
def count_isolated_islands(matrix):
rows, cols = len(matrix), len(matrix[0])
def dfs(x, y):
if x<0 or y<0 or x>=rows or y>=cols or matrix[x][y]!=1:
return 0
matrix[x][y] = 0
area = 1
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
area += dfs(x+dx, y+dy)
return area
total = 0
for i in range(1, rows-1):
for j in range(1, cols-1):
if matrix[i][j] == 1:
total += dfs(i, j)
return total
102. 島の沈没
孤立島を水没させ（1を0に変更）、変更後の行列を出力します。
def sink_isolated_islands(grid):
rows, cols = len(grid), len(grid[0])
def mark_non_isolated(x, y):
if 0<=x<rows and 0<=y<cols and grid[x][y]==1:
grid[x][y] = 2
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
mark_non_isolated(x+dx, y+dy)
# 端の島をマーク
for i in range(rows):
mark_non_isolated(i, 0)
mark_non_isolated(i, cols-1)
for j in range(cols):
mark_non_isolated(0, j)
mark_non_isolated(rows-1, j)
# 孤立島を沈没
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
grid[i][j] = 0
elif grid[i][j] == 2:
grid[i][j] = 1
return grid
</code>103. 水流問題
特定のセルから水が両方の境界に到達できるかを判定します。
def water_flow(matrix):
rows, cols = len(matrix), len(matrix[0])
pacific = [[False]*cols for _ in range(rows)]
atlantic = [[False]*cols for _ in range(rows)]
def dfs(x, y, ocean):
ocean[x][y] = True
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
nx, ny = x+dx, y+dy
if 0<=nx<rows and 0<=ny<cols and not ocean[nx][ny] and matrix[nx][ny]>=matrix[x][y]:
dfs(nx, ny, ocean)
# 太平洋（左と上）から到達可能なセル
for i in range(rows):
dfs(i, 0, pacific)
for j in range(cols):
dfs(0, j, pacific)
# 大西洋（右と下）から到達可能なセル
for i in range(rows):
dfs(i, cols-1, atlantic)
for j in range(cols):
dfs(rows-1, j, atlantic)
# 両方に到達可能なセルを返す
return [(i,j) for i in range(rows) for j in range(cols) if pacific[i][j] and atlantic[i][j]]
104. 最大島の構築
1つの0を1に変更した後、可能な最大の島の面積を求めます。
def largest_island_after_flip(grid):
rows, cols = len(grid), len(grid[0])
island_id = 2
area_map = {}
def dfs(x, y, id):
if x<0 or y<0 or x>=rows or y>=cols or grid[x][y]!=1:
return 0
grid[x][y] = id
area = 1
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
area += dfs(x+dx, y+dy, id)
return area
# 各島にIDを割り当てて面積を記録
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
area = dfs(i, j, island_id)
area_map[island_id] = area
island_id += 1
max_area = max(area_map.values()) if area_map else 0
# 各0セルをチェック
for i in range(rows):
for j in range(cols):
if grid[i][j] == 0:
connected = set()
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
nx, ny = i+dx, j+dy
if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]>1:
connected.add(grid[nx][ny])
current = 1 + sum(area_map[id] for id in connected)
max_area = max(max_area, current)
return max_area
105. 有向グラフの到達可能性
ノード1から全てのノードに到達可能かどうかを判定します。
def is_fully_reachable(n, edges):
graph = [[] for _ in range(n+1)]
for s, t in edges:
graph[s].append(t)
visited = [False]*(n+1)
queue = [1]
visited[1] = True
count = 1
while queue:
node = queue.pop()
for neighbor in graph[node]:
if not visited[neighbor]:
visited[neighbor] = True
count += 1
queue.append(neighbor)
return 1 if count == n else -1
106. 島の周長
島の周囲の長さを計算します。
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
perimeter += 4
if i>0 and grid[i-1][j]==1:
perimeter -= 2
if j>0 and grid[i][j-1]==1:
perimeter -= 2
return perimeter