# collections モジュールから deque クラスをインポートする
from collections import deque
# 入力
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
# スタート地点とゴール地点の探索
for y in range(H):
for x in range(W):
# スタート地点のとき
if A[y][x] == 'S':
sy = y
sx = x
# ゴール地点のとき
if A[y][x] == 'G':
gy = y
gx = x
# キューの宣言
queue = deque()
# すべてのマスを -1（未探索）で初期化
distance = [[-1] * W for _ in range(H)]
# 探索用の変数
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# キューに追加しない条件にあたるか判定する関数
def is_skip(next_y, next_x):
# 移動できるマスが盤面外のとき
if (next_y < 0 or H <= next_y) or (next_x < 0 or W <= next_x):
return True
# 移動できるマスが探索済みのとき
if distance[next_y][next_x] != -1:
return True
# 移動できるマスが壁のとき
if A[next_y][next_x] == '#':
return True
return False
# 幅優先探索
def bfs(sy, sx):
# スタート地点をキューに追加する
queue.append([sy, sx])
# スタート地点の距離を0にする
distance[sy][sx] = 0
# キューが空になるまで繰り返す
while queue:
# キューの先頭の要素を取り出す
y, x = queue.popleft()
# 先頭の要素から上下左右への処理
for i in range(4):
# 現在地点から移動できるマス
next_y = y + dy[i]
next_x = x + dx[i]
# 移動できるマスをキューに追加しないとき
if is_skip(next_y, next_x):
continue
# 移動できるマスをキューに追加する
queue.append([next_y, next_x])
# 移動できるマスの距離を現在のマスの距離+1にする
distance[next_y][next_x] = distance[y][x] + 1
# スタート地点から幅優先探索
bfs(sy, sx)
# 答えの出力
print(distance[gy][gx])
人の視線を考慮する
幅優先探索で最短距離を求めることができました。
あとは、人の視線を探索するフィールドに落とし込むことができればいいです。
入力例１の説明の、次の図を作ることができれば、幅優先探索するだけになります。
E – Avoid Eye Contact 入力例１
入力として与えられる A について、視線を反映させて上図のようにしていきます。
視線を反映させる処理については、未実装ですが次のようなコードでよさそうです。
for y in range(H):
for x in range(W):
# 右向きの人
if A[y][x] == '>':
# 視線をフィールドに反映させる処理
# 下向きの人
if A[y][x] == 'v':
# 視線をフィールドに反映させる処理
# 左向きの人
if A[y][x] == '<':
# 視線をフィールドに反映させる処理
# 上向きの人
if A[y][x] == '^':
# 視線をフィールドに反映させる処理
視線を反映させる処理については関数に切り出して実装します。
向いている方向に伸ばすための変数 dy と dx を使うことで、各方向に向いている人について対応できるようにしています。
# 視線をフィールドに反映させる処理の関数
def update_field(y, x, dy, dx):
# 障害物や別の人にあたるまで繰り返す
while True:
# 向いている方向に1マス伸ばす
y += dy
x += dx
# 盤面外のとき
if (y < 0 or H <= y) or (x < 0 or W <= x):
break
# 障害物や別の人にあたったとき
if A[y][x] == '#' or A[y][x] in '>v<^':
break
# フィールドに視線（！）を反映
A[y][x] = '!'
視線を反映させるコードについてのみをまとめると次のようなコードになります。
# 入力
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
# 視線をフィールドに反映させる処理の関数
def update_field(y, x, dy, dx):
# 障害物や別の人にあたるまで繰り返す
while True:
# 向いている方向に1マス伸ばす
y += dy
x += dx
# 盤面外のとき
if (y < 0 or H <= y) or (x < 0 or W <= x):
break
# 障害物や別の人にあたったとき
if A[y][x] == '#' or A[y][x] in '>v<^':
break
# フィールドに視線（！）を反映
A[y][x] = '!'
for y in range(H):
for x in range(W):
# 右向きの人
if A[y][x] == '>':
update_field(y, x, 0, 1)
# 下向きの人
if A[y][x] == 'v':
update_field(y, x, 1, 0)
# 左向きの人
if A[y][x] == '<':
update_field(y, x, 0, -1)
# 上向きの人
if A[y][x] == '^':
update_field(y, x, -1, 0)
# 確認用の出力
print(A)
