問題概要

$H \times W$ のグリッドにおいて、以下の操作が施されたものが入力として与えられます。

はじめ、グリッドのすべてのマスの文字は '.' である
グリッドの部分長方形であって縦横のサイズがそれぞれ 2 以上であるものを選び、その内部のマスをすべて '#' にする
その部分長方形に含まれるマスを 1 つだけ選んで '.' にする

最後に選ばれたマスを求めてください。

入力例

5 6
......
..#.#.
..###.
..###.
......

この場合は、上から 2 行目、左から 4 列目が答え

制約

$2 \le H, W \le 500$

解法 (1)：僕の本番でやった解法

次の 2 ステップに分けて考えます。

ステップ 1：部分長方形を特定する
ステップ 2：部分長方形内部のマスをすべて調べて、文字 '.' であるものを探す

ステップ 1 は次の 4 つの値を求めることで達成できます。

min_x： $x$ 行目に文字 '#' が含まれるような最小の $x$
max_x： $x$ 行目に文字 '#' が含まれるような最大の $x$
min_y： $y$ 列目に文字 '#' が含まれるような最小の $y$
max_y： $y$ 列目に文字 '#' が含まれるような最大の $y$

これによって、長方形領域が $O(HW)$ の計算量で求められます。

ステップ 2 は簡単です。求めた長方形領域の各マスを探索して、文字 '.' であるマスを見つければよいです。この部分も $O(HW)$ の計算量で実行できます。

全体として、 $O(HW)$ の計算量で解けます。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
    
    // 長方形領域を求める
    int minx = H, maxx = -1, miny = W, maxy = -1;
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            if (S[x][y] == '#') {
                chmin(minx, x), chmax(maxx, x), chmin(miny, y), chmax(maxy, y);
            }
        }
    }
    
    // 長方形領域内部の空きマスを探す
    for (int x = minx; x <= maxx; ++x) {
        for (int y = miny; y <= maxy; ++y) {
            if (S[x][y] == '.') {
                cout << x+1 << " " << y+1 << endl;
                return 0;
            }
        }
    }
}

解法 2：天才解法

もう 1 つ、実装が楽になる天才的な解法がある！　次の条件を満たすマスを探すだけで OK！！

文字が '.' である
上下左右に隣接するマスのうち、文字が '#' であるものが 2 個以上ある

計算量は $O(HW)$ となります。

コード

#include <bits/stdc++.h>
using namespace std;

// 上下左右への移動を表す変数
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) cin >> S[i];
   
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            // 文字 '.' でなければスキップ
            if (S[x][y] != '.') continue;
            
            // 上下左右の隣接する '#' の個数を数える
            int num = 0;
            for (int dir = 0; dir < 4; ++dir) {
                int x2 = x + dx[dir], y2 = y + dy[dir];
                if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
                if (S[x2][y2] == '#') ++num;
            }
            if (num >= 2) {
                cout << x+1 << " " << y+1 << endl;
                return 0;
            }
        }
    }
}