Submission #280084

---

Source Code Expand

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 入力処理
row, column = map(int, raw_input().split())
sy, sx = map(int, raw_input().split())
gy, gx = map(int, raw_input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
DATA = [raw_input() for i in range(row)]


# 行けるかどうか２次元配列に格納
map_lst = [[-1 for j in range(column)] for i in range(row)]
for i in xrange(row):
    for j in xrange(column):
        if DATA[i][j] == ".":
            map_lst[i][j] = map_lst[i][j] = 0

# スタート、ゴールの設定
map_lst[sy][sx] = 1
map_lst[gy][gx] = 1

# print map_lst

# 幅優先探索
import Queue
q = Queue.Queue()
q.put(sy)
q.put(sx)
q.put(0)   # [state, depth]
checked = []
while not q.empty():
    current_statey = q.get()
    current_statex = q.get()
    current_depth = q.get()

    # すでに通っている
    if [current_statey, current_statex] in checked:
        continue

    # 途中経過
    # print ([current_statey, current_statex], current_depth)

    # ゴール
    if [current_statey, current_statex] == [gy, gx]:
        print(current_depth)
        break

    # 次の状態を求める
    current_depth += 1
    if map_lst[current_statey][current_statex + 1] >= 0:
        q.put(current_statey)
        q.put(current_statex + 1)
        q.put(current_depth)
    if map_lst[current_statey][current_statex - 1] >= 0:
        q.put(current_statey)
        q.put(current_statex - 1)
        q.put(current_depth)
    if map_lst[current_statey - 1][current_statex] >= 0:
        q.put(current_statey - 1)
        q.put(current_statex)
        q.put(current_depth)
    if map_lst[current_statey + 1][current_statex] >= 0:
        q.put(current_statey + 1)
        q.put(current_statex)
        q.put(current_depth)

    # 通ったリストに追加
    checked.append([current_statey, current_statex])

Submission Info

Judge Result