解説

各マス、既に戦闘した魔物使いの組 $(i,j,S)$ を頂点として考える。マス $(i,j)$ からマス $(i',j')$ へ移動するとき、マス $(i',j')$ を見ている魔物使いの集合を $S'$ とすると、$(i,j,S) \rightarrow (i',j',S \cup S')$ の有向辺を張ることができる。このようにしてできた有向グラフ $G$ について、$(1,1,\emptyset)$ から $(H,W,S)$ までの経路が存在するような $S$ の集合 $S \subset U$ のうち、 最も要素数の少ないものが答えとなる。

• 各マスについてそのマスを見ている魔物使いの集合を求める ... $O(N \times max(H,W))$
• 有向辺張り ... $O(HW \times 2^N)$
• BFS,DFS ... $O(V+E) = O(HW \times 2^N)$ $(V = HW \times 2^N , E = 4 \times (HW \times 2^N))$