自己紹介
大阪大学2回生で競技プログラミング部rainbou副部長、Atcoder緑
X:https://x.com/e4h99rhQ7I24670
問題文 島探し (paizaランク S 相当) URL
解説
この問題はSランク問題のなかでは基礎的な問題だと思います。特に、初めてSランク問題に挑戦さあれる方には特におすすめです。
Atcoderで出題されればおそらくdiff400くらいだろうと思われます。
解法自体は非常にシンプルでUnionFindや幅優先探索などなんでも解けると思います。ここでは、一番簡単で分かりやすいであろう幅優先探索を使った解説をしていきます。
グリッド上を全探索し1が出てきたらansを+=1してそこに隣接している1のマスを0に変えていけばいいです。その後、変更されたマスをqueに入れてを繰り返しやっていく感じになります。
計算量はO(HW)です。
※ここでは入力例にあったN, Mを用いずにH, Wとしています。これは多くのグリッド問題がH, Wを用いるため、それにのっとって、ほかの問題に応用の聞きやすいようにしています。
実装例
from queue import Queue
W, H = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
ans = 0
DIJ = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def in_board(x, y):
if 0 <= x < H and 0 <= y < W:
return True
return False
def bfs(i, j):
que = Queue()
que.put((i, j))
A[i][j] = 0
while not que.empty():
i, j = que.get()
for di, dj in DIJ:
x, y = i+di, j+dj
if not in_board(x, y):
continue
if A[x][y] == 0:
continue
A[x][y] = 0
que.put((x, y))
for i in range(H):
for j in range(W):
if A[i][j] == 0:
continue
ans += 1
bfs(i, j)
print(ans)