[Algorithm] BaekJoon : 19238. タクシー台

[問題のショートカット]https://www.acmicpc.net/problem/19238

📌問題の説明

StartLinkは「StartTaxi」というタクシー事業を開始した.タクシーを起動するのは特別で、お客さんを目的地に送るたびに燃料が充電され、燃料が切れた当日の仕事は終わります.
タクシー運転手の崔伯俊さんは今日、M人の乗客を乗せることを目標にしています.白俊が活動する分野はNだ.×Nサイズのメッシュで表すことができ、各セルが空または壁になっています.タクシーが空席の場合、上下左右に隣接する空席の一つに移動できます.アルゴリズム経験豊富なBaek Junは,特定の位置に移動すると常に最短経路に移動する.
M人の乗客は1つのスペースに立って、別のスペースの1つに移動する準備をしています.複数の乗客が一緒に搭乗する場合はありません.そのため、白俊は乗客1人を乗せて目的地に向かうM回を繰り返した.乗客一人一人が動かず、出発地でタクシーに乗るしかなく、目的地の地下タクシーに乗るしかありません.
白俊が乗る乗客を選ぶ時、現在の位置で最も短い距離の乗客を選ぶ.このような乗客が多い場合は、その中で一番小さい番号の乗客を選び、そのような乗客が多い場合は、その中で一番小さい番号の乗客を選びます.タクシーと乗客が同じ位置に立っている場合、その乗客までの最短距離はゼロです.燃料は1コマ移動するごとに消費される.1人の乗客を目的地に移動することに成功すると、その乗客が移動中に消費する燃料量は2倍に増加する.移動途中で燃料が切れて移動が失敗し、当日の作業が終了します.乗客を目的地に移すと同時に、燃料が尽きた場合は失敗しない.

<図1>タクシーが活動するエリアを示す地図で、タクシーと3人の乗客の出発地と目的地を示す.タクシーの現在の燃料量は15です.現在、タクシーから乗客1人あたりの最短距離は9、6、7なので、タクシーは2番の乗客の出発地に向かいます.

<図2>タクシーから2番乗客の出発地までの経路を示し、<図3>2番乗客の出発地から目的地までの経路を示す.目的地に移動する前に消費される燃料は6であり、移動後に12を充電するので、残りの燃料量は15である.現在、タクシーから乗客1人あたりの最短距離は7つなので、タクシーは2つの中でもっと小さい1番の乗客の出発地に移動します.

<図4>及び<図5>は、タクシー1号の乗客が目的地へ向かう経路を示す.余剰燃料量15-7-7+7×2=15.

<図6>および<図7>は、タクシー3号の乗客が目的地に向かう経路を示す.最終残存燃料量15-5-4+4+4×2=14.
すべての乗客を正常に送ることができるかどうかを見つけて、送ることができるならば、プログラムを書いて最終的な余剰燃料の量を出力してください.
入力
第1列は、N、Mおよび初期燃料の量を与える.(2≦N≦20,1≦M≦N 2,1≦初期燃料≦500000)燃料は無限に充填できるので、初期燃料の量を超えて満タンになる可能性がある.
次の行から、N行において、伯俊活動領域の地図が与えられる.0はスペース、1は壁です.
次の行は白俊が運転を始めた車両の行番号と列番号を示した.行と列番号は1以上N以下の自然数で、運転を開始したのはスペースです.
次の行から、各乗客の出発地の行と列番号、および目的地の行と列番号.すべての出発地と目的地は空いていて、出発地ごとに異なり、お客様の出発地と目的地ごとに異なります.
しゅつりょく
すべてのお客様を動員し、燃料が満たされたときに残りの燃料の量を出力します.しかし、移動途中で燃料が尽き、次の出発地または目的地に移動できない場合は、−1が出力される.すべてのお客様を移動できなくても、-1を出力します.

💡 問題を解く

これはBFS+シミュレーションタイプの問題である.
壁がなければ簡単に行・列座標で距離を計算できますが、壁があるのでBFSで最短距離を求めます.
その後、乗客を乗せて、目的地に移動し、燃料の部分を変えて、問題のように表現すればよい.
問題を解く順番は以下の通りです.

タクシーの位置を基準にBFSで距離を求めます.

乗っていない乗客

名を対象に、最寄りの乗客を探しています.

街近くで運賃の小さい乗客を選んだ.

行が同じであれば、熱値の小さい乗客を選択します.

の余剰燃料と乗客との距離を比較する.

は、余剰燃料<乗客距離−出力−1が停止している場合に行う.

の場合、燃料残量>乗客距離、燃料残量−乗客距離.

の乗客位置を基準にBFSで距離を求める.

に搭載された乗客番号と同じ目的地までの距離を見つける.

は、余剰燃料<目的地までの距離−1出力が停止している場合に行う.

余剰燃料>目的地までの距離であれば、余剰燃料+目的地までの距離である.乗客を

目的地に乗せた後、対応する乗客番号に表示を完了し、タクシーの行、列を更新する.

コードは次のとおりです.

import sys
from copy import deepcopy
from collections import deque

d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def pick(distance):
    man = -1 # 선택한 승객의 번호
    now = int(1e9)
    for idx in range(M):
        if not done[idx]:
            r, c = customer[idx][0], customer[idx][1]
            if distance[r][c] < now: # 거리가 작으면 갱신
                now = distance[r][c]
                man = idx
            elif distance[r][c] == now: # 거리가 같으면
                if r < customer[man][0]: # 행 값이 작은 승객을 선택
                    man = idx
                elif r == customer[man][0]: # 행 값도 같으면
                    if c < customer[man][1]: # 열 값이 작은 승객을 선택
                        man = idx
    return man

def bfs(tr, tc): # 최단 거리 구하기
    queue = deque([(tr, tc)])
    distance = deepcopy(origin) # 거리를 표시할 행렬
    distance[tr][tc] = 1
    while queue:
        r, c = queue.popleft()
        for idx in range(4):
            nr = r + d[idx][0]
            nc = c + d[idx][1]
            if 0 <= nr < N and 0 <= nc < N:
                if not distance[nr][nc]:
                    queue.append((nr, nc))
                    distance[nr][nc] = distance[r][c] + 1
    return distance

N, M, fuel = map(int, input().split())
origin = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
customer = []
tr, tc = map(int, input().split()) # 택시의 행, 열
tr -= 1; tc -= 1 # 인덱스는 0부터 이므로 1씩 빼주었다.

for _ in range(M):
    sr, sc, er, ec = map(int, input().split())
    customer.append((sr-1, sc-1, er-1, ec-1)) # 승객의 행, 열 / 목적지의 행, 열

done = [False] * M # 승객 탑승 여부를 알려주는 배열
while done.count(False): # 모든 승객을 이동시키지 않았다면 아래의 내용을 반복 
    distance = bfs(tr, tc) # 택시 ~ 승객 거리 찾기
    man = pick(distance) # 가까운 승객 선택
    dist_man = distance[customer[man][0]][customer[man][1]] # 승객까지의 거리
    if not dist_man or fuel < dist_man - 1: # 만약 벽으로 인해 갈 수 없거나 남은 연료보다 거리가 더 크면
        fuel = -1 # -1을 출력하고 탐색 중지
        break
    fuel -= (dist_man - 1) # 이동이 가능하면 연료값 최신화

    distance = bfs(customer[man][0], customer[man][1]) # 택시(with 승객) ~ 목적지 거리 찾기
    dist_goal = distance[customer[man][2]][customer[man][3]] # 목적지 까지 거리
    if not dist_goal or fuel < dist_goal - 1: # 이동 가능 여부 확인
        fuel = -1
        break
    fuel += dist_goal - 1 # 연료값 최신화

    done[man] = True # 승객 이동 여부 최신화
    tr, tc = customer[man][2], customer[man][3] # 택시 위치(행, 열) 최신화
print(fuel)

乗客を目的地に移動するにはBFSを2回行う必要があるため,メモリを増やすことでBFS探索の時間的複雑さを低減しようとしたが,このコードも完全に通過できる.👍