結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
17,952 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
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, s = map(int, input().split())
g, g = map(int, input().split())
maze = [','.join(input()).split(',') for i in range(M)]

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

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

for i in range(N):
    for j in range(M):
        if maze[j][i] == 'S':
            lists = queue([j, i, 0])

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

# ここから幅優先探索
while loop:
    *now, times = lists.dequeue()
    if now[0] == None:
        break
        
    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