けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 305 C - Snuke the Cookie Picker (4Q, 灰色, 300 点)

AtCoder AtCoder300点 ABC-C 灰色diff 二次元グリッド 二次元配列 for文 多重for文 制約条件:長方形領域 全探索 易しい全探索 NoviSteps4Q

楽な実装がないかと探す系の問題

問題概要

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;
            }
        }
    }
}