Witch at Home

できるだけ魔法を使わずに移動

まず、魔法を使わないで移動できる範囲を求めます。
各マスの領域ごとではなく、マスの角ごとに管理します。マス目全体の周も考えると、 $2W+1 \times 2W+1$ の大きさになります。それぞれを頂点と呼ぶことにします。
ある頂点から隣り合う頂点に遷移できない条件は、ある $2$ つのマスの両方に木が生えていることです。
これらに注意して BFS (幅優先探索)をすると、正しく求められます。

魔法による特殊な移動

次に、魔法を $1$ 回使うときの BFS の動作を考えます。
$1$ 回魔法を使うことは、 BFS ですでに遷移している各頂点から、

• 上下方向に $h$ 回以下、無条件に遷移できる
• 左右方向に $w$ 回以下、無条件に遷移できる

として遷移することとみなせます。
これを高速に実現するために、元の BFS とはそれぞれ別のテーブルを用いて

• $h$ 回まで上下方向に遷移できる BFS ( $2$ 段階目の BFS)
• $w$ 回まで左右方向に遷移できる BFS ( $3$ 段階目の BFS)

を行います。
これは、距離テーブルの代わりに「あと何回遷移できるか」を記録すれば可能です。
以上、全体で $3$ 段階の BFS をします。

アルゴリズムの全体像・ $O(W^3)$ 解

$3$ 段階の BFS を繋げて動作させるには、ある段階で到達できた頂点をそのまま次の段階の BFS のキューに追加すればよいです。 $3$ 段階目から $1$ 段階目に戻るときも同じです。
この $3$ 段階の $1$ 周分は $O(W^2)$ 時間でできます。
求めるものは、 $1$ 段階目の距離テーブルの外周に初めて来た時に何周していたかです。
高々 $W$ 周なので全体で $O(W^3)$ 時間です。

距離テーブルの再利用・ $O(W^2)$ 解

$1$ 段階目の距離テーブルは明らかに再利用できます。
$2$ 段階目と $3$ 段階目は距離テーブルの再利用には注意が必要です。
例えば、 $3$ 段階目で到達した頂点から、 $1$ 段階目・ $2$ 段階目の BFS で全く移動できない場合、次の $3$ 段階目ではすでに到達した頂点から探索する必要があります。
図はそれを表す距離テーブルの例です。 0 の頂点から改めて探索しないと $2$ 周目で外周 . に到達しないことに注意してください。

入力, 1周目, 2周目
3 3 1 1   .......    .......
######    .xxxxx.    .01110.
######    ..010x.    .o1110.
.#####    ..010x.    .o1110.
######    .x010x.    .01110.
######    .xxxxx.    .01110.
######    .......    .......

どの頂点を再度探索すればよいかは、 $1$ 次元的に考察でき、その結果「あと $1$ 回以上移動できる」状態の頂点を再探索することは「あと $0$ 回移動できる」状態の頂点の再探索でカバーできます。
前回の探索で「あと $0$ 回移動できる」状態になった頂点のみ探索しなおせば十分です。

各段階の BFS では各頂点は高々 $2$ 回しか探索しないので、全体で $O(W^2)$ 時間になります。