はじめに
こんにちは。今回は「電脳少女プログラミング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」は単なるプログラミング問題集ではなく、新しい学びや発見につながる場だと感じました。
みなさんもぜひ挑戦してみてください！どんなフィードバックが返ってくるか楽しみですね。