本日は暇な時の時間潰しにぴったりな
方形を数えるプログラムについてです


解説動画はこちら




問題

次の図形の中に正方形または長方形は
幾つあるでしょうか?
(黒塗りの部分が図形で 5x3 マスです)







探索プログラムの考え方


今回は四角形を探索するプログラムです

図形を黒を1 白を0でデータ化したのち
黒塗りの部分で作られる方形が
幾つあるのかを左上から順番に数えていきます。

起点を左上とし、そこから縦と横に
1マスずつ伸ばして数えていきます。

途中白(0)があったら探索を抜けて次に進みます。

こんな感じで探していきます。




方形を数えるコード

コードはこんな感じになります。

import matplotlib.pyplot as plt
import numpy as np

# 指定された左上(top, left)を基準に黒い長方形を数える
def count_black_rectangles_from_top_left(grid, top, left):
    # 左上が黒でなければカウントしない
    if grid[top][left] != 1:
        return 0  
    rows, cols, count = len(grid), len(grid[0]), 0
    
    # 指定された左上から長方形を探索
    for bottom in range(top, rows):
        for right in range(left, cols):
            # 長方形内がすべて黒かを確認
            if all(grid[i][j] == 1 for i in range(top, bottom + 1) for j in range(left, right + 1)):
                count += 1
            else:
                # 白いセルが見つかったらその方向は探索不要
                break  
    return count

# グリッド内のすべての黒い長方形を数える
def count_black_rectangles(grid):
    rows, cols, total_count = len(grid), len(grid[0]), 0
    for top in range(rows):
        for left in range(cols):
            total_count += count_black_rectangles_from_top_left(grid, top, left)
    return total_count

# グリッドのプロット
def plot_grid(grid):
    plt.figure(figsize=(6, 4))
    plt.imshow(np.array(grid), cmap="binary", interpolation="nearest")
    plt.title("Grid Visualization")
    plt.axis("off")
    plt.show()

# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [1, 1, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 1, 0],
]
plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")

ぜひGoogle Colabなどにコピペして
試してみてください

もっと大きな16x16でやると
こうなります。

# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
]

plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")

何個あるのかは数えてみてくださいね

こういった探索プログラムは
アルゴリズムを考える基本にもなり
プログラミングの上達にも役立ちますね!!!


今回は暇つぶしにぴったりな
方形を数えるプログラムについてでした

それでは

タグ ：

#プログラミング

#Python

#探索

#正方形

#長方形