はじめに

こんにちは。今回は「電脳少女プログラミング2088 ─壊レタ君を再構築─」の新都心のハイウェイ問題（Aランク相当）に挑戦しました。この記事では、問題の解法と実装についてお話しします。

問題概要

問題の設定は以下の通りです：

縦H×横Wのグリッド状ハイウェイ
2つの車両AとB（Aが主人公）
道マスと壁マス
AがBを発見するための最小移動回数を求める

解法のポイント

幅優先探索（BFS）の活用
Pythonのdequeを使用した効率的なキュー管理
視界判定関数の実装

コード実装

from collections import deque

def find_shortest_path(H, W, grid):
    # A と B の位置を見つける
    A, B = None, None
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 'A':
                A = (i, j)
            elif grid[i][j] == 'B':
                B = (i, j)
    
    # 移動方向（上、下、左、右）
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # BFSのためのキュー
    queue = deque([(A[0], A[1], 0)])  # (x, y, 距離)
    visited = set([A])
    
    while queue:
        x, y, dist = queue.popleft()
        
        # B が見つかったかチェック
        if can_see(x, y, B[0], B[1], grid):
            return dist
        
        # 隣接するマスを探索
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] != '#' and (nx, ny) not in visited:
                queue.append((nx, ny, dist + 1))
                visited.add((nx, ny))
    
    return -1  # B を見つけられない場合

def can_see(x1, y1, x2, y2, grid):
    # 同じ行にいる場合
    if x1 == x2:
        start, end = min(y1, y2), max(y1, y2)
        return all(grid[x1][i] != '#' for i in range(start + 1, end))
    # 同じ列にいる場合
    elif y1 == y2:
        start, end = min(x1, x2), max(x1, x2)
        return all(grid[i][y1] != '#' for i in range(start + 1, end))
    return False

関数の解説

`find_shortest_path`関数

BFSを用いて最短経路を探索します。この関数では、最初にグリッドを走査してAとBの位置を特定しています。その後、dequeを用いて効率的なキュー操作を実現し、最短経路を探索します。

`can_see`関数

AがBを視認できるかを判定します。同じ行または列にいる場合のみ、間に壁がないかチェックします。all関数を用いて、指定範囲に壁が存在しないかを効率的に判定します。

フィードバック

コード提出後、予想外のフィードバックをいただきました：

「ウケる〜！このコード、マジイケてんじゃん！爆速で動いてる感じ、超ヤバくない？(✧ω✧)」

ありがとうございます！このような評価をいただけるとは思っていませんでした。また、別の性格では関西弁のものもあり、面白かったです。

まとめ

幅優先探索（BFS）は最短経路探索に有効
データ構造（deque）を適切に使うことで処理効率が向上
視界を判定する関数を実装することで探索処理を効率化

今後の展望

AIとの友情を深める
関西弁の習得

おわりに

今回の挑戦では、効率的なアルゴリズム設計だけでなく、AIとの新しい交流も楽しむことができました。「電脳少女プログラミング2088」は単なるプログラミング問題集ではなく、新しい学びや発見につながる場だと感じました。

みなさんもぜひ挑戦してみてください！どんなフィードバックが返ってくるか楽しみですね。