簡単に言うと、移動の仕方 (マス目とハンコの縦方向及び横方向のずれ)、回転の仕方 (\(4\) 方向) を全て試して、ハンコの底面が障害物のあるマスに重ならないようなものがあるかを探します。
このときハンコを、入力で与えられたような行列形式で持つと実装が面倒になりがちです。一旦、# であるようなマスの座標を持ったリスト(配列)形式にした方が実装が楽だと思います。

ハンコの \(90\) 度回転は各座標を \((x, y)\) を \((y, -x)\) で置き換えればよいです。
回転をしてもハンコの \(x, y\) 座標は \(-\max(H, W)\) 以上 \(\max(H, W)\) 以下に収まるので、マス目とハンコの縦方向及び横方向のずれは \(-2\max(H, W)\) 以上 \(2\max(H, W)\) 以下を調べれば十分です。

障害物に重ならないかの判定に \(O(HW)\) かかって時間計算量は \(O(H^2W^2)\) です。