【競技プログラミング:リハビリ】二分探索(上下左右方向)

既存投稿一覧ページへのリンク

一覧ページ

雑記

ボンバーマンみたいなゲーム制作に使えそうな問題ですので、Unityとか使えるようC#でもまとめておくかな。

サンプルコード

python

sample_code.py

def find_first_true(start, grid, direction):
    """
    起点から指定方向に探索し、最初にTrueが見つかる座標を返します

    Args:
        start (tuple): 探索起点座標 (row, col)
        grid (list): 2次元の真偽値リスト
        direction (str): 探索方向 'r', 'l', 'u', 'd'

    Returns:
        tuple or None: 最初のTrue座標（見つからない場合はNone）
    """
    row, col = start
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0

    # 各方向の探索範囲を設定
    if direction == 'r':
        for c in range(col + 1, cols):
            if grid[row][c]:
                return (row, c)
    elif direction == 'l':
        for c in range(col - 1, -1, -1):
            if grid[row][c]:
                return (row, c)
    elif direction == 'u':
        for r in range(row - 1, -1, -1):
            if grid[r][col]:
                return (r, col)
    elif direction == 'd':
        for r in range(row + 1, rows):
            if grid[r][col]:
                return (r, col)
    
    return None

if __name__=="__main__":
    grid = [
        [False, False, True, False],
        [False, True,  False, False],
        [False,  False, False, True]
    ]

    # 例1: (0,0)から右方向探索 → (0,2)を返す
    print(find_first_true((0,0), grid, 'r'))  # (0, 2)

    # 例2: (1,2)から上方向探索 → (0,2)を返す
    print(find_first_true((1,2), grid, 'u'))  # (0, 2)

    # 例3: (2,3)から左方向探索 → (2,3)の左にTrueなし → None
    print(find_first_true((2,3), grid, 'l'))  # None

関連問題