グリッドが二部グラフであることを利用し、以下のような bit DP を考えます。

\(\mathrm{DP}[i][j][k]=(i,j)\) にいて、集合 \(k\) の爆弾を全て解除した時のあり得る現在時刻の最小値、ただし達成不可能の場合は \(\infty\) とする。

この場合、計算量は共に \(\mathrm{O}(HW2^N)\) となり間に合いません。

ここで、マス目の集合 \(S\) を「 \((1,1)\ +\) 爆弾のあるマス目」とし、\(S\) の中のマス目の距離を前もって求めておきます。計算量は \(\mathrm{O}(NHW+N^2)\) となります。

そうすると、bit DP を以下のようにできます。

\(\mathrm{DP}[i][j]=S\) の中の \(i\) 番目のマスにいて、集合 \(j\) の爆弾を全て解除した時のあり得る現在時刻の最小値、ただし達成不可能の場合は \(\infty\) とする。

この場合、計算量が \(\mathrm{O}(2^NN^2)\) となりこの問題を解くことができます。