なんとなく解き方あったなと思ったのでやってみました。
マップのある場所の四方を調べる的なことなので、マップの廻りを何かで取り囲んでやると場合分けが少なくなる的なことです。
H, W = map(int, input().split())
BORDERED = tuple(
(True,) * (W + 2)
if j == 0
or j == H + 1
else
(True
, *(i == "#" for i in input())
, True
)
for j in range(H + 2)
)
every_side_surrounded = (
(j - 1, i - 1)
for j in range(1, H + 1)
for i in range(1, W + 1)
if BORDERED[j - 1][i]
and BORDERED[j + 1][i]
and BORDERED[j][i - 1]
and BORDERED[j][i + 1]
)
for p in every_side_surrounded:
print(p[0], p[1])