F - I want to eat Cookies!

この問題では巡回セールスマン問題、BFSを問います。

最初にクッキーマスが1つの時は、通常のBFS（幅優先探索）を用いることで容易に答えを得ることができます。
その場合は「始点 $(1,1)$ からクッキーマスまでに要する移動回数の最小値」+「クッキーマスから終点 $(H,W)$ までに要する移動回数の最小値」として求めることができます。

I. 巡回セールスマン問題への帰着

次に、クッキーマスの個数 $n$ として $n\ge 2$ の場合を考えてみます。その場合、すべてのクッキーマスを通過する必要があるのでその分の移動回数を考慮する必要があります。
これを厳密に式として示すために、初めに $n$ 個あるクッキーマスそれぞれに番号 $C_1,C_2,\dots C_n$ と振っておきます。そして $i\ (1\le i\le n)$ 番目のクッキーマス $C_i$ のマスを $\text{grid}(C_i)=(c_h ,c_w)$ と表すものとします。

このように定義すると、$1$ から $n$ までの順列 $P=(P_1,P_2,\dots, P_n)$ に対して、求める答えは

• $\text{dist}(S, C_{P_1})+\text{dist}(C_{P_1}, C_{P_2})+\dots+\text{dist}(C_{P_{n-1}}, C_{P_n})+\text{dist}(C_{P_n}, G)$

の、最小値を取ったものになります。ただし $\text{dist}(a, b)$ で、マス $a$ からマス $b$ までの移動回数の最小値を、$S$ は始点、$G$ は終点を表すマスを表します。

以上の式によって、本問題で求める値は判明しました。
上の式から、順列 $P$ の並び方さえ考えることができればこの問題を解くことができます。

しかし制約から「クッキーマスの個数は $15$ 以下」となっており、順列 $P$ の並びは最大で $15!$ 通り存在し、これをすべて試すと時間制限には間に合いません。
つまりこの問題は、「すべてのクッキーマスをどのように巡回するか？」といった、俗に言う巡回セールスマン問題（TSP）を解くということになります。

II. TSPをbitDPで解く

今回の $n\le 15$ という小さい制約を利用しながら巡回セールスマン問題を解く解法として、bitDPというアルゴリズムを用いることが挙げられます。
bitDPでは、今まで通過してきたマスを「集合」として捉えながら動的計画法(DP)を適用していくといったアプローチをとります。つまりビットの知識を取り扱います。
今回は解説の都合上、細かい説明は省略しますが、自身で調べてみると良いと思われます。

本解説のセクション I. で説明した通り、クッキーマスにはそれぞれ番号を振り分けました。これを利用することで

• $\text{dp}[S][c]:=$ クッキーマスを通過したときの整数集合 $S$ として、最後に通過したクッキーマスの番号が $c\ (1\le c\le n)$ であったときの、あり得る移動回数の最小値

と定義することができます。
ただし $c$ はクッキーマスに対して任意に振り分けた番号です（それぞれの番号からマスを一意に特定することができればどんな番号でも構いません）。

DP遷移式の説明をします。その前に次の配列 $\text{dist}$ を定義しておきます：

• $\text{dist}[c][h][w]:=$ クッキーマス $c$ のマスから $(h,w)$ にたどり着くまでに必要な移動回数の最小値

この値はBFSによって前計算します。この時の計算量は最悪 $O(HW)$ ですが、値の取得では $O(1)$ となります。

次にDP配列の初期化について、これは次のようになります。

• $\text{dp}[2^c][c]=\text{dist}[c][0][0]\ (1\le c\le n)$

これは始点 $(1,1)$ からクッキーマス $c$ までの距離として初期化しています※1。
他の初期値については

• $2^{1},2^{2},\dots, 2^{n}$ を除くすべての整数集合 $s\ (1\le s\lt 2^n)$ ※2および $1\le i\le n$ に対して $\text{dp}[s][i] = \infty$

として初期化することが適切です※3。

次に遷移式についてです。結果のみを記しますが次のように遷移することが適切です：

• $\text{dp}[s \cup 2^{\text{nxt}}][\text{nxt}]=\min (\text{dp}[s \cup 2^{\text{nxt}}][\text{nxt}], \text{dp}[s][\text{pre}] + \text{dist}[\text{pre}][c_{\text{nxt}_h}][c_{\text{nxt}_w}])\ (1\le s\lt 2^n)$

ただし $\text{nxt}$ は次に向かうクッキーマスの番号、$\text{pre}$ は一つ前に通過したクッキーマスの番号を表します。
またクッキーマス $c_\text{nxt}$ のマスは $(\text{nxt}_h, \text{nxt}_w)$ としています※4。
（感覚的には「クッキーマス $\text{nxt}$ を、現時点で見た時に入れる方が最適な方法となるか？」というような形です。）

このアプローチによって、すべてのクッキーマスを通過した場合の移動回数の最小値は、$1\le c\le n$ に対して $\text{dp}[2^n-1][c]$ となります。
この場合「始点 $(1,1)$ から始めてすべてのクッキーマスを通過した時の、最後に通過したクッキーマスの番号が $c$ であるときの移動回数の最小値」ということになります。
つまりこの時点では始点からすべてのクッキーマス、までに関する距離のみを計算していることになり、終点までの距離は考慮されていないことになります。

III. 終点までの距離との合算

では終点までの距離はどのように算出すればよいでしょうか？
この算出する式は、前のセクション II. で得た値を基にして次のように表せます：

• ★：「始点からすべてのクッキーを拾い終えた時点での要する距離」+「最後に拾ったクッキーマスから終点までの要する距離」

この式はセクション I. で表した答えの式と一致します。
さらに最小値の和は、最小性を満たすことになるということからそれぞれの距離の最小値さえ求められれば、この問題を解くことができます。

★における前者の答えは $\min_{1\le i\le n} \text{dp}[2^n-1][i]$ として、後者については前者を満たす $i(=i_\ast)$ において、$\text{dist}[i_\ast][H][W]$ が答えとなります。

結局、求める答えは

• $\min_{1\le i\le n} (\text{dp}[2^n-1][i]+\text{dist}[i][H][W])$

となります。
この方針で実装することで、全体で計算量は $O(HW+2^{n}n^2)$ となり、今回は $n\le 15$ なので十分高速です。

以上で本問題を解くことができます。

コーナーケースとして、クッキーマスが一つも存在しないケースの処理をする必要があることに注意してください。

解答例(C++):

※1
通常の巡回セールスマン問題では最初に1つだけ始点を設定しますが、今回は始点がどのクッキーマスにもなり得るのでこのようにすべての「点」で初期化をしておきます。

※2
ビット表現として見ると、$1\le c\le n$ のうち $2^c$ という値は「クッキーマス $c$ を通過している」ということを表しています。
今回は任意のクッキーマスをただ一つ通過している、ということが前提なのでこのような初期化になっています。
参考までにビット表現の説明を下記に記します：

• 全体のクッキーマスの個数が $5$ であるとして、
• クッキーマス（番号 $c=2$）を通過したときの整数は $2^2=4$
• なので下位 $3$ ビット目のフラグが立つ

（0-indexed表記になっていることに注意）

0：00000
4：00100

• 同様に $c=4$ の場合の整数は $2^4=16$
• なので下位 $5$ ビット目のフラグが立つ

0：00000
16：10000

• クッキーマス（番号 $2,4$）を通過した場合の整数は $2^2+2^4=4+16=20$
• なので下位 $3,5$ ビット目のフラグが立つ

0：00000
20：10100

※3
$\infty$ となっていますが、これは今回解く問題が最小値問題であるためです。

※4
つまり $\text{dist}[\text{pre}][c_{\text{nxt}_h}][c_{\text{nxt}_w}]$ は「一つ前に通過したクッキーマス $\text{pre}$ から次に向かうクッキーマス $\text{nxt}$ のマスまでに要する移動回数の最小値」を表すことになります。

Tips

この問題の類題は AtCoder:ABC301-E などが挙げられます。
こちらの問題は「～回以内の移動で」と書かれていますが、本質は変わりません。