まず、素直な方針として、次のアルゴリズムがまず考えられる解法だと思います。

• \(1 \leq a \lt b \leq H, 1 \leq c \lt d \leq W\) を満たす範囲の整数の組 \((a,b,c,d)\) について, 次の条件を満たすかを判定する。
  • \((a, b)\) を左上, \((c, d)\) を右下とする長方形領域内部の . の個数を調べる。
  • . がちょうど 1 個だった場合、そのマスがすぬけ君がクッキーを取ったマスになる。

しかしこのアルゴリズムは 6 乗の for-loop を必要とするため時間計算量が \(\mathrm{O}(H^3 W^3)\) となり非常に遅いです。どうにか高速化する方法を考えましょう。

重要な気づきとして、次の事実があります。

• \(U\) を(クッキーが置かれている行の番号の最小値) とする。このとき、すぬけ君がクッキーを食べる前と食べた後で、\(U\) の値は変わらない。

(証明) 部分長方形は縦横ともに 2 マス以上の大きさがあります。よって、すぬけ君がクッキーを食べる前の時点で最上段のクッキーは 2 個以上あります。すぬけ君はクッキーを 1 個しか食べないので、すぬけ君がクッキーを食べた後も最上段のクッキーは 1 個以上残っています。よって \(U\) の値もまた変わりません。(証明終わり)

同様の考え方で、次の 3 つの値もクッキーを食べる前と食べた後で変わらないことが分かります。

• \(D :=\) (クッキーが置かれている行の番号の最大値)
• \(L :=\) (クッキーが置かれている列の番号の最小値)
• \(R :=\) (クッキーが置かれている列の番号の最大値)

よって、次のような方針のアルゴリズムでこの問題を解くことができます。

• \(U, D, L, R\) を求める。これは全てのマスについて全探索すれば計算できる。
• \((U, L)\) を左上、\((D, R)\) を右下とする部分長方形の範囲で . になっているマスが答えである。

時間計算量は \(\mathrm{O}(HW)\) で、AC するのに十分高速です。

• 実装例(C++)

#include <algorithm>
#include <iostream>
using namespace std;

int H, W, U = 1e9, D = -1e9, L = 1e9, R = -1e9;
char S[502][502];

int main() {
  cin >> H >> W;
  for (int i = 0; i < H; i++) cin >> S[i];

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (S[i][j] == '#') {
        U = min(U, i), D = max(D, i);
        L = min(L, j), R = max(R, j);
      }
    }
  }
  for (int i = U; i <= D; i++) {
    for (int j = L; j <= R; j++) {
      if (S[i][j] == '.') cout << i + 1 << " " << j + 1 << endl;
    }
  }
}