The naivest solution that you may come up with is as follows:

• For all integer tuples \((a,b,c,d)\) such that \(1 \leq a \lt b \leq H, 1 \leq c \lt d \leq W\):
  • Count the number of .s in the rectangular region whose top-left and bottom-right squares are \((a, b)\) and \((c, d)\), respectively.
  • If there is exactly one ., then that square is the one Snuke took a cookie from.

However, this algorithm requires a six-fold nested loop, so its time complexity is \(\mathrm{O}(H^3 W^3)\), which is too slow. How can we optimize it?

An important observation follows:

• Let \(U\) be the minimum index of a row with a cookie. Then, \(U\) remains the same even after Snuke eats the cookie

(Proof) the sub-rectangle has a width and height of at least two. Thus, there are two or more cookies in the topmost row. Since Snuke eats only one cookie, there remains one or more cookies on the topmost row. Therefore, \(U\) is invariant too. (End of proof)

Similarly, the following three values also remain unchanged after he eats a cookie:

• \(D :=\) (the maximum index of a row with a cookie)
• \(L :=\) (the minimum index of a column with a cookie)
• \(R :=\) (the maximum index of a column with a cookie)

Hence, the following algorithm solves the problem.

• Find \(U\), \(D\), \(L\), and \(R\). This can be done by scanning the entire grid.
• The answer is the .-square within the sub-rectangle whose top-left and bottom-right squares are \((U, L)\) and \((D, R)\), respectively.

The time complexity is \(\mathrm{O}(HW)\), which is fast enough to get AC (accepted).

• Sample code (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;
    }
  }
}