結果

問題 No.3063 幅優先探索
ユーザー konchanksukonchanksu
提出日時 2020-04-01 22:35:30
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,535 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 33,792 KB
最終ジャッジ日時 2024-06-27 11:49:37
合計ジャッジ時間 4,014 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
16,128 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 31 ms
10,880 KB
testcase_05 RE -
testcase_06 AC 165 ms
28,160 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# キュークラスの作成
class queue:
    def __init__(self, *item):
        self.queue = [i for i in item]
        self.top = len(self.queue)
    
    def enqueue(self, *item):
        self.queue += [i for i in item]
    
    def dequeue(self):
        try:
            _, *self.queue = self.queue
            return _
        except:
            return [None, None, None]

N, M = map(int, input().split())
s, s1 = map(int, input().split())
g, g2 = map(int, input().split())
maze = [','.join(input()).split(',') for i in range(M)]

maze[s1 - 1][s - 1] = 'S'
maze[g2 - 1][g - 1] = 'G'

# 次進む方向一覧
d = [[0, 1], [1, 0], [-1, 0], [0, -1]]

lists = queue([s - 1, s1 - 1, 0])

loop = True           
gone = [[False for i in range(N)] for j in range(M)] 

# ここから幅優先探索
while loop:
    *now, times = lists.dequeue()

    for i in d:
        next_to = [i + j for i, j in zip(now, i)]
        
        # はみ出るかどうか
        if next_to[0] < 0 or next_to[0] >= M or next_to[1] < 0 or next_to[1] >= N:
            continue
            
        # すでにいったことがあるかどうか
        if gone[next_to[0]][next_to[1]]:
            continue
        
        # ゴールかどうか
        if maze[next_to[0]][next_to[1]] == 'G':
            print(times + 1)
            loop = False
            break
            
        # 道かどうか
        if maze[next_to[0]][next_to[1]] == '.':
            gone[next_to[0]][next_to[1]] = True
            lists.enqueue(next_to + [times + 1])
0