paizaS問題の解答をManimで動画化する

はじめに

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

入力例2

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