実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 272

問題概要

$H \times W$ のマス目があり、上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表す。各マスの状態は文字 $S_{i,j}$ で表され、 $S_{i,j} =$ # のときそのマスは机、.のときそのマスは床である。床のマスは2つ以上存在することが保証される。

これから床のマスから異なる2マスを選び、加湿器を設置することにする。加湿器が設置されたとき、あるマス $(i,j)$ は加湿器があるマス $(i',j')$ からのマンハッタン距離が $D$ 以下であるときに限り加湿される。ここで、加湿器が置かれた床のマスは必ず加湿されている。

加湿される床のマスの個数として考えられる最大値を求めよ。

制約

$H,W,D$ は整数。
$1 \leq H, W \leq 10$
$2 \leq H \times W$
$0 \leq D \leq H+W-2$

考察

$H, W$ の制約が小さいので、全探索が使えそう。具体的には、以下のような処理となる。

床のマスを配列floorsに格納しておく。
floorsの中から加湿器を設置するマスを2つ選ぶ。これを $A, B$ とする。
それぞれに対して、次の操作を行う。
- floorsの各マスを走査し、 $A$ (または $B$ ) とのマンハッタン距離が $D$ 以下ならカウンターを1増やす。
カウンターをこれまでの最大値と比較・更新。
最終的な最大値を出力。

計算量としては、 $A, B$ の選択のすべての場合を行うのに $O((HW)^2)$ 、 $A, B$ それぞれとすべての床マスとのマンハッタン距離の計算に $O(HW)$ 、合計 $O((HW)^3)$ となるが、今回の制約下では十分高速である。

B問題にしてはforループのネストが多めなので、適宜処理を別の関数に分割していった方が良さそう。

コード

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

using Pair_int = pair<int, int>;

#define all(x) (x).begin(), (x).end()

// ======================================== //

int dist(int x1, int y1, int x2, int y2)
{
    return abs(x1 - x2) + abs(y1 - y2);
}

int calc(const vector<Pair_int> &floors, int x1, int y1, int x2, int y2, int D)
{
    set<pair<int, int>> cells;
    for (const auto &cell : floors)
    {
        if (dist(cell.first, cell.second, x1, y1) <= D)
        {
            cells.insert(cell);
        }
    }
    for (const auto &cell : floors)
    {
        if (dist(cell.first, cell.second, x2, y2) <= D)
        {
            cells.insert(cell);
        }
    }

    return cells.size();
}

int main()
{
    int H, W, D;
    cin >> H >> W >> D;
    vector<string> S(H);
    vector<Pair_int> floors;

    rep(i, 0, H)
    {
        cin >> S[i];

        rep(j, 0, W)
        {
            if (S[i][j] == '.')
            {
                floors.emplace_back(i, j);
            }
        }
    }

    int ans = 0;
    int n = floors.size();
    rep(i, 0, n)
    {
        rep(j, i + 1, n)
        {
            int x1 = floors[i].first, y1 = floors[i].second;
            int x2 = floors[j].first, y2 = floors[j].second;

            int cnt = calc(floors, x1, y1, x2, y2, D);
            chmax(ans, cnt);
        }
    }

    cout << ans << endl;
}