5
2

はじめに

paizaとQiitaのコラボキャンペーンで出題されたSランク問題の中で、島探しという問題の入力から出力までを動画にしました。動画作成には、3Blue1Brownの動画作成に使われているManimというライブラリを使用。

前提知識

下記を知っているという前提で話していきます

  • BFS(幅優先探索)

おすすめ記事

島探し

問題

ひとくち解説

グラフ全体をたどっていき黒いマスへ止まるごとにBFS(DFSでもOK)をします。探索しきったときにcntをインクリメントをし、最後にcntを表示します。

正解したコード

island.py
from collections import deque


m, n = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]  # グラフ

dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 移動方向
visited = set()  # ここに移動したマスを格納し、再度探索しないようにする
cnt = 0
# BFS
for i in range(n):
    for j in range(m):
        # 白いマスか、訪れたことがあるマスならcontinue
        if g[i][j] == 0 or (i, j) in visited:
            continue
        que = deque([(i, j)])
        visited.add((i, j))
        while que:
            # pi, pjは現在地
            pi, pj = que.popleft()  # ここをpopにするとDFSになる
            for di, dj in dij:
                # 四方向を探索、ni, njは次探索するマス
                if 0 <= (ni := pi + di) < n and 0 <= (nj := pj + dj) < m:
                    if g[ni][nj] == 0 or (ni, nj) in visited:
                        continue
                    que.append((ni, nj))
                    visited.add((ni, nj))
        cnt += 1  # 移動できる点がなくなったらインクリメント

print(cnt)

正解したコードを動画化

paizaの入力例1, 2を動画化!

入力例1
TableBFS1_m.gif

入力例2
TableBFS2_m.gif

Manimのコード

manim.py
from manim import *
from collections import deque

# Manim部分のみコメント
class TableBFS(Scene):
    def construct(self):
        m, n = map(int, input().split())
        g = [list(map(int, input().split())) for _ in range(n)]

        # gridをテーブルにする
        table = MathTable(
            [[str(cell) for cell in row] for row in g], include_outer_lines=True
        ).scale(0.8)

        # テーブルを表示
        self.play(Create(table))
        self.wait(1)

        # カウントを表示
        cnt_text = Text("Count: 0").next_to(table, UP)
        self.play(Write(cnt_text))

        dij = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        visited = set()
        cnt = 0
        for i in range(n):
            for j in range(m):
                if g[i][j] == 0:
                    # 訪問した点が0のときグレーで塗りつぶす
                    self.play(
                        table.get_cell((i + 1, j + 1)).animate.set_fill(
                            GRAY, opacity=0.5
                        )
                    )
                    continue
                if (i, j) in visited:
                    continue
                que = deque([(i, j)])
                visited.add((i, j))
                while que:
                    pi, pj = que.popleft()
                    # 訪問した点が1のとき赤で塗りつぶす
                    self.play(
                        table.get_cell((pi + 1, pj + 1)).animate.set_fill(
                            RED, opacity=0.5
                        )
                    )
                    self.wait(0.1)
                    for di, dj in dij:
                        if 0 <= (ni := pi + di) < n and 0 <= (nj := pj + dj) < m:
                            if g[ni][nj] == 0 or (ni, nj) in visited:
                                continue
                            que.append((ni, nj))
                            visited.add((ni, nj))
                cnt += 1

                # カウントアップ
                new_cnt_text = Text(f"Count: {cnt}").next_to(table, UP)
                self.play(ReplacementTransform(cnt_text, new_cnt_text))
                cnt_text = new_cnt_text


# このコマンドで実行
# manim -pqm --format gif manim.py < input.txt TableBFS
5
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
2