結果

問題 No.8063 幅優先探索
コンテスト
ユーザー konchanksu
提出日時 2020-04-01 22:21:11
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,671 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 33,664 KB
最終ジャッジ日時 2024-06-27 11:25:57
合計ジャッジ時間 3,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 1 WA * 3 RE * 2 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

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:
        print('No')
        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