[python]ゲームマップ最短距離

問題の説明

RORゲームは2チームに分かれて行い、先に相手陣営を破壊すれば勝つゲームです.そのため、各チームはできるだけ早く相手陣営に到着したほうがいい.
これからはチームのメンバーになってゲームをします.以下に、5×5サイズのマップで、キャラクタが(行:1、列:1)、相手陣営が(行:5、列:5)の位置にある例を示します.

上図では、黒い部分は壁に塞がれて歩けない道で、白い部分は歩ける道です.キャラクターが移動するときは東、西、南、北に1コマずつ移動し、ゲームマップから離れることはできません.
次の例では、キャラクタが相手の陣営に向かう2つの方法を示します.

最初の方法は11格子を経て相手陣営に到着した.

第2の方法は15格子を経て相手陣営に到着する.

上記の例では、第1の方法ほど相手陣営に早く到達する方法はないので、相手陣営に向かう最も速い方法である.
相手が自分の陣営の周りに壁を立てたら、相手の陣営に届かないかもしれない.たとえば、次の場合、キャラクタは相手の陣営に到達できません.

ゲームマップのステータスマップをパラメータとして与える場合は、solution関数を完了し、キャラクタを相手陣営が通過する必要がある格子数の最大値に戻します.でも相手陣営に届かない時は-1に戻ってください

マイ解答(複数使用)

import collections
import heapq
def solution(maps):
    n , m = len(maps) , len(maps[0])
    big_map = [0] * (n+2) * (m+2)
    cur_list = []
    cursor = m + 3
    start , fin = [m+3 , (n+2)*(m+2) - m - 4]
    
    # 7*7 행렬제작 후 기존 maps에 한겹 더 둘러싸기
    for i in range(len(maps)):
        for j in maps[i]:
            cur_list.append(cursor)
            big_map[cursor] = j
            cursor +=1
        cursor += 2

    # 그래프 인접 리스트 구성
    graph = collections.defaultdict(list)
    for k in cur_list:
        if big_map[k] == 1:
            if big_map[k-(m+2)] == 1:  # 상
                graph[k].append(k-(m+2))
            if big_map[k-1] ==1 :  # 좌
                graph[k].append(k-1)
            if big_map[k+1] == 1:  # 우
                graph[k].append(k+1)
            if big_map[k+m+2] == 1: # 하
                graph[k].append(k+m+2) 
                
    # 큐 변수: [(거리, 정점)]
    Q = [(1,start)]
    
    dist = collections.defaultdict(int)
    
    # 우선순위 큐 최솟값 기준으로 도착점까지 최소 거리 판별
    while Q:
        result, node = heapq.heappop(Q)
        if node == fin:
            return result
        
        if node not in dist:
            dist[node] = result
            for v in graph[node]:
                alt = result + 1
                heapq.heappush(Q,(alt,v))
                
    return -1

まず、基本的に提供される地図では、さらに0を囲んで矩形を形成する.そして地図の値を真ん中に置きます.(0回り)

そして,n*m個の矩形の各格子をノードと見なし,グラフ隣接表を作成した.それを1の場所しか行けない場所と見なしてディクシャナにしました.(defaultdictを使用)

多極値アルゴリズムを用いて最短経路を求めた.

distという名前のディックシャナを使用して、最短距離に達したノード(セル)に再アクセスできないように設定し、頂点が必要な到着地と一致している場合は、その時点の最小値を返すように設定します.

また、whileゲートが目的地に到達できなければ目的地に到達できないため、-1に戻る.