上から \(i\) 行目、下から \(j\) 列目の部屋を \((i,j)\) と書くことにします。
\(K\) で場合分けして、条件を満たすような壁の選び方について考えます。

\(K<H+W-2\) のとき

\((1,1)\) から \((H,W)\) まで最短でも \(H+W-2\) 回の移動が必要なので、\(0\) 通りです。

\(K=H+W-2\) のとき

\((1,1)\) から \((H,W)\) に最短で移動する方法の場合の数に等しく、これは \(\binom{H+W-2}{H-1}\) 通りです。

\(K=H+W-1\) のとき

\((1,1)\) から \((H,W)\) の最短経路と、そこに含まれない壁 \(1\) 個の選び方に等しく、これは \(\binom{H+W-2}{H-1}\times(H(W-1)+(H-1)W-(H+W-2))\) 通りです。

\(K=H+W\) のとき

最短経路長は \(H+W-2\) か \(H+W\) のいずれかです。

最短経路長が \(H+W-2\) の場合を考えます。
\((1,1)\) から \((H,W)\) の最短経路に使われる壁 \(H+W-2\) 個と、それ以外の壁 \(2\) 個を選んだ時、最短経路が \(2\) 通りあるようなものだけ二重にカウントされます。 最短経路が \(2\) 通りある選び方は、 \(\\(i,j)\rightarrow(i,j+1)\rightarrow(i+1,j+1)\\ (i,j)\rightarrow(i+1,j)\rightarrow(i+1,j+1)\)
の壁がすべて選ばれる \((i,j)\) が存在するような選び方であり、これは、\((1,1)\) から \((H-1,W-1)\) への最短経路とその経路に含まれる部屋 \(1\) 個の選び方と一対一で対応するため、\(\binom{H+W-4}{H-2}\times(H+W-3)\) 通りです。

最短経路長が \(H+W\) の場合を考えます。
縦と横のちょうど一方で \((H,W)\) から遠のく方向に \(1\) 度だけ移動することになります。
その方向が縦の場合を考えます。 最短経路長が \(H+W\) であるとき、この移動の前後は横方向に移動していたことになります。 ここで、この \(\text{横縦横}\) の動きを \(\text{縦'}\) と置き換えると、\(\text{縦}\) を \(H+1\) 個、\(\text{横}\) を \(W-3\) 個並べて、\(2\) 番目から \(H\) 番目の \(\text{縦}\) のうち一つを \(\text{縦'}\) に置き換える方法に対応していることがわかります。
遠のく方向が横の場合も同様に解くことができます。