AtCoder ABC 269 B - Rectangle Detection (6Q, 灰色, 200 点)

二次元配列の基本問題！　ただし、問題文の意味を理解するのが少し大変かもしれない。

• 問題へのリンク

問題概要

のグリッドがある。グリッドの各文字は最初はすべて '.' である。今、

• 
• 

を満たす整数 をとり、 かつ を満たすマス の文字を '#' へと書き換えた。

書き換えたあとのグリッドが与えられるので、 の値を求めよ。

解法

入力例 1 は次のようになっている。

..........
..........
..........
..........
...######.
...######.
...######.
...######.
..........
..........

これは、上から 5 行目から 8 行目まで、左から 4 行目から 9 行目までの文字が '#' であるため、答えは となる。

これらの値を特定するためには、次の値を求めればよい。

• minx ← マス の値が '#' である最小の
• maxx ← マス の値が '#' である最大の
• miny ← マス の値が '#' である最小の
• maxy ← マス の値が '#' である最大の

このとき、 の値はそれぞれ minx, maxx, miny, maxy とすればよい。

コード

ここでは、マス を 0-indexed で求めているため、最後に minx などの値に 1 を足して出力している。

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

int main() {
    vector<string> S(10);
    for (int x = 0; x < 10; ++x) cin >> S[x];
    
    int minx = 10, maxx = -1, miny = 10, maxy = -1;
    for (int x = 0; x < 10; ++x) {
        for (int y = 0; y < 10; ++y) {
            if (S[x][y] == '#') {
                minx = min(minx, x);
                maxx = max(maxx, x);
                miny = min(miny, y);
                maxy = max(maxy, y);
            }
        }
    }
    cout << minx + 1 << " " << maxx + 1 << endl;
    cout << miny + 1 << " " << maxy + 1 << endl;
}