LCP 13.

問題出典：パワーバックル

問題

宝の地図を入手し、迷宮の中にまだ世に知られていない宝があることを発見。

迷路は2次元の行列で、文字列の配列として表されます。迷路は、文字列の配列で表現された2次元マトリックスです。しかし、宝はいくつもの隠された器官によって守られています。マップ上にはいくつもの器官ポイントがあり、すべての器官が作動しなければ宝には到達できません。

仕掛けが作動しないようにするには、仕掛けの上に重い石を置く必要があります。迷路にはいくつかの石の山があり、それぞれに仕掛けを作動させるのに十分な数の重い石が無限にあります。しかし、石はとても重いので、一度に一つの石しか指定された場所に移動させることができません。

この迷路にも、壁の中に入ってはいけない壁がいくつかあります。それ以外は自由に通行できます。岩山、仕掛け、始点、終点も通行可能です。

各ステップは上下左右に1マスずつ移動でき、迷路の外に出ることはできません。石を上下に動かしても歩数には入りません。では、スタート地点から、最後に宝を手に入れるために最低限必要な歩数は何歩でしょうか？宝を手に入れることができなければ、-1に戻ります。

例1：

入力：["S#O", "M..", "M.T"]
出力：16

解説： 最適ルートは次の通り：S->O、コスト＝4、石を移動しに行く O->2列目のM、コスト＝3、Mのメカニズムが発動、M->2列目のO、コスト＝3、石を移動するためにOに戻る必要あり。 番目の列のO->M、コスト＝4、これですべてのメカニズムが発動。 番目の列のM->T、コスト＝2、宝を取りにTへ。 合計16ステップ。

例2：

入力：["S#O", "M.#", "M.T"]
出力：-1
解説：石を動かしてメカニズムを作動させることができない。

例3：

入力：["S#O", "M.T", "M.."]
出力：17
解説：終点も通過可能であることに注意。

制限事項

• 1 <= maze.length <= 001
• 1 <= maze[i].length <= 001
• maze[i].length == maze[j].length
• S 結果は1つだけ
• <= M <= 16
• 0 <= Oの数 <= 40, タイトルは、Mが迷路に存在するとき、少なくとも1つのOが存在することを保証しています。

アイデア

アイデア：状態圧縮動的計画法

まず、出発点 Sから 終点 Tまで迷路の中を歩くという問題です：

• '#' ，
• '.'合格
• M」：重い石でないと発動しないオルガンポイントを示します。
• O:石の山を表し、1回の移動で動かせる石は1つだけ。重い石は無制限.

この場合、終点 Tに 到達するためには、すべてのオルガンポイント Mを トリガーして、終点に到達するための最小ステップ数を求める必要があります。

設問では、キャラクターは4方向に動くことができると書かれています。上記の質問概要に基づくと、考えられるシナリオは以下のようになります：

• M メカニズムを作動させるには重い石が必要なので、 Sから Mに 直接行くことはできません ；
• Oから Mへ 重い石を持ち上げると、そのメカニズムが作動します。
• Mから Oまで 、玉石を動かし続けます。
• Mから 最後まで T すべての臓器がトリガーされると、最後まで行くことができます。

この問題では、終点に到達するための最短の歩数を尋ねています。つまり、2点間の最短距離は、上記の可能なシナリオを考慮することで、その後の計算のために算出することができます。

ここで、まず最初に取り組むべきことは、どのようなルートで重い石を取りに行き、メカニズムを起動させるかということです。ここではまず一般的な分析を：

上記の可能性を見てみると、Sからスタートして、あるOを通過し、重い石を手に入れ、あるMに到達し、そこでメカニズムが作動するはずです。ここで、あるMに対して、SからOを経由してMまでの距離が最短となるようなOが存在するはずです。つまり、Mを固定してOを列挙すれば、Sから各Mまでの最短距離を求めることができるのです。

Mポイントは複数あるかもしれません。そして、あるM点に到達した後、再びあるO点に行って重い石を手に入れ、他のM点を回ってメカニズムを起動させ、すべてのメカニズムが起動するまで移動する必要があります。ここで、私たちが最初にM1に到達し、メカニズムM2を起動するために重い石を手に入れる必要があるとすると、M1からM2までの最短距離を見つけるためにOを列挙することもできます。

すべての臓器がトリガーされたら、あとはMからTまでの距離を計算するだけです。

上記は一般的な分析で、それぞれのケースで最短距離を計算し、全体の最短距離を求めるものです。ただし、ここで注意しなければならないのは、すべてのオルガンポイントMをトリガーする必要があるため、Mをトリガーする順番が異なると、異なる結果になるということです。

先ほどの分析によると、ある迷路では、器官が作動してもしなくても、それぞれの位置から他の位置までの距離は変わりません。そこで、BFSの考え方を用いて、ある点から別の点までの距離を計算します。

臓器 Mi から Mj までの最短距離を保持する 2 次元配列を定義します.

dp[mask][i]は現在i番目のMの位置にいることを表し、現在の状態がマスクの最短距離であることを表します。機構の状態にはトリガー状態と非トリガー状態の2種類があります。

すべての臓器がトリガーされると、最後にトリガーされた臓器の地点から終点までの最短距離を比較して最短距離を決定します。

具体的な実装コードは以下の通り。

コード実装

from typing import List
class Solution:
 def minimalSteps(self, maze: List[str]) -> int:
 # つの方向
 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
 m = len(maze)
 n = len(maze[0])
 # 開始点、終了点
 start_x, start_y, end_x, end_y = -1, -1, -1, -1
 # メカニズム、石積み
 buttons = []
 stones = []
 # まず、迷宮の文字の意味をマークする。
 for i in range(m):
 for j in range(n):
 if maze[i][j] == 'M':
 buttons.append((i, j))
 elif maze[i][j] == 'O':
 stones.append((i, j))
 elif maze[i][j] == 'S':
 start_x = i
 start_y = j
 elif maze[i][j] == 'T':
 end_x = i
 end_y = j
 # 臓器と石積みの数
 num_b = len(buttons)
 num_s = len(stones)
 # 始点から他のすべての位置までの距離を計算する。
 start_to_any_pos = self.bfs(start_x, start_y, maze, m, n, directions)
 # 岩山がない場合は、始点から終点までの最短距離を求める。
 if num_b == 0:
 return start_to_any_pos[end_x][end_y]
 # ある臓器から別の臓器、始点と終点までの距離を記録する配列を定義する。
 # dist[i][num_b] 始点までの距離を示す，dist[i][num_b+1] 終点までの距離を示す
 dist = [[-1] * (num_b + 2) for _ in range(num_b)]
 # 迷宮内には、複数の機構Mが存在する可能性がある。機構を起動した後、各機構Mが終点に到達する距離を計算する。
 # im 臓器から他の点までの距離を記録する
 button_to_any_pos = []
 for i in range(num_b):
 b_x, b_y = buttons[i]
 # 番目の臓器Mから他の点までの距離を計算し、ボタンに格納する。_to_any_pos  
 button_to_any_pos.append(self.bfs(b_x, b_y, maze, m, n, directions))
 # 臓器から終点までの距離
 dist[i][num_b+1] = button_to_any_pos[i][end_x][end_y]
 # 始点から各器官までの距離を計算する。
 for i in range(num_b):
 # S Mまでの距離
 start_to_m = -1
 for j in range(num_s):
 s_x, s_y = stones[j]
 # 器官を固定し、出発点Sから各石の山を通って器官までの距離を計算する。
 # 臓器から始点Sまでの距離として理解することもでき、これは変数ボタン_to_any_pos  
 if button_to_any_pos[i][s_x][s_y] != -1 and start_to_any_pos[s_x][s_y] != -1:
 # 距離を計算し、最小値を比較する。
 tmp = button_to_any_pos[i][s_x][s_y] + start_to_any_pos[s_x][s_y]
 if start_to_m == -1 or start_to_m > tmp:
 start_to_m = tmp
 # S から M までの最短距離を dist 配列に入れる。
 dist[i][num_b] = start_to_m
 # ここではi番目の臓器からj番目の臓器までの距離を計算する。
 # 例：M1がOを通過し、M2に最短距離で到達する。
 for j in range(i+1, num_b):
 m_to_another_m = -1
 for k in range(num_s):
 s_x, s_y = stones[k]
 if button_to_any_pos[i][s_x][s_y] != -1 and button_to_any_pos[j][s_x][s_y] != -1:
 tmp = button_to_any_pos[i][s_x][s_y] + button_to_any_pos[j][s_x][s_y]
 if m_to_another_m == -1 or m_to_another_m > tmp:
 m_to_another_m = tmp
 # 距離は無向グラフなので、2点間の距離は対称である。
 dist[i][j] = m_to_another_m
 dist[j][i] = m_to_another_m
 
 # 出発点から臓器に到達できない場合、または臓器点から終点に到達できない場合は、経路がないことを意味し、-1を返す。
 for i in range(num_b):
 if dist[i][num_b] == -1 or dist[i][num_b+1] == -1:
 return -1
 
 # dp配列を定義し、-1はトラバースした状態を意味する。
 # Mがn個あり、臓器の状態が2であるとする。^n  
 # dp[mask][i] 現在位置がi番目のMであり、現在の状態がマスクの最短距離であることを示す。
 dp = [[-1] * num_b for _ in range(1<<num_b)]
 # バイナリ形式のマスクで表現
 # 初期化、S から i 番目の臓器まで、マスクの i 番目のビットは 1、他のビットは 0。
 # 先に計算した値をdp配列に代入する。
 for i in range(num_b):
 dp[1<<i][i]=dist[i][num_b]
 
 # トラバースを開始し、マスクの異なる状態における各器官点 i の値を計算する。
 # mask インデックスは1から始まる
 for mask in range(1, (1<<num_b)):
 for i in range(num_b):
 # 現在のdpが合法である場合
 if mask & (1<<i) != 0:
 for j in range(num_b):
 # 次の臓器 j を選択する。j がまだトリガーされていない場合、マスク内の j の位置は 0 でなければならない。
 if mask & (1<<j) == 0:
 next_mask = mask | (1<<j)
 tmp = dp[mask][i] + dist[i][j]
 if dp[next_mask][j] == -1 or dp[next_mask][j] > tmp:
 dp[next_mask][j] = tmp
 # ここでは、すべての臓器がトリガーされた後、最後の臓器から終点までの距離を計算し、最も小さい値をとる。
 ans = -1
 final_mask = (1<<num_b) - 1
 for i in range(num_b):
 tmp = dp[final_mask][i] + dist[i][num_b+1]
 if ans == -1 or ans > tmp:
 ans = tmp
 
 return ans
 def bfs(self, x, y, maze, m, n, directions):
 """ある点から別の点までの距離を計算する
 """
 res = [[-1] * n for _ in range(m)]
 # 点を始点に設定する。
 res[x][y] = 0
 
 from collections import deque
 queue = deque()
 queue.append([x, y])
 while queue:
 # キューから、点と点の間の距離を計算する。
 cur_x, cur_y = queue.popleft()
 # 境界を制限し、4方向に移動し、通行可能な場所と未訪問の場所に出会ったら移動し、距離を記録する。
 for dx, dy in directions:
 nx = cur_x + dx
 ny = cur_y + dy
 if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] != '#' and res[nx][ny] == -1:
 res[nx][ny] = res[cur_x][cur_y] + 1
 queue.append([nx, ny])
 return res
maze = ["S#O", "M..", "M.T"]
solution = Solution()
solution.minimalSteps(maze)

出版物