障害物がないマスを、\(\mathrm{O}(H+K)\) 個の矩形領域に分解します。各列に対して連続している障害物がないマスの区間を極大に取るとよいです。

矩形領域同士で隣り合っているペアの個数が \(\mathrm{O}(H+K)\) 個であることが証明できます。(横方向に連続していることはなく、縦方向に連続しているペアの個数は \(i,i+1\) 行目に矩形領域が \(k_i,k_{i+1}\) 個あったとき高々 \(k_i + k_{i+1}\) ペアしかないことから従います。または、このグラフの平面性から示してもよいでしょう。)

よって、後はグラフを実際に構築して \((1,1)\) を含む矩形領域から \((H,W)\) を含む矩形領域に到達可能かを見ればよいです。計算量は \(\mathrm{O}(H+W+K)\) です。