バックアップアルゴリズム2468号:安全区域

リンク

https://www.acmicpc.net/problem/2468

質問する

防災庁は大雨の雨季に備えて、次のようなことを計画しています.まず、ある地域の高度な情報を理解します.そして、この地域が大雨の時に最大でどれだけの浸水しない安全区域を形成できるかを調べます.このとき,問題を単純化するために,雨季の雨量が一定の高さ以下のすべての場所が水没すると仮定した.
一部の領域の高さ情報は、行と列のサイズがそれぞれNの2次元配列の形で与えられ、配列内の各要素は、その点の高さを表す自然数である.例えば、以下はN=5の領域の高さ情報である.
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
現在、上のような地域では大雨が降っており、4より低いところはすべて水没しています.この場合、水没点は以下のようにグレーで表される.
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
水没しない安全区域とは、水没しない場所が上、下、右または左に隣接し、その大きさが最も大きい区域を指す.上記の場合、水没しない安全区域は5つある(死点付着のみとは思えない2つの地点が隣接している).
また、上記の地域で大雨が降って高さ6以下のすべての場所が水没した場合、水没しない安全区域は、下図のように4つ確認できます.
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
このように雨季によって降雨量が異なり、水没しない安全区域の個数も異なる.前例のように雨量によってすべての状況を調べた結果,水没しない安全区域の個数のうち最大は5であった.
地域の高さ情報を取得する場合は、雨季に浸水しない安全な地域の最大数を計算するプログラムを作成します.

入力

1行目は、ある領域の2次元配列を表す行数と列数Nを入力する.Nは2以上100以下の整数である.2行目からN行目まで、2次元配列の1行目からN行目までの高さ情報を順次入力します.各行において、各行の第1列から第N列までのN個の高さ情報を表す自然数がスペースを隔てて入力される.高さは1以上100以下の整数です.

しゅつりょく

第1行は雨季に浸水しない安全区域の最大数を出力する.

入力と出力の例

プールコード（C++）

#include <iostream>
#include <algorithm>
#include <math.h>
#include <memory.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define MAX 101
using namespace std;

int n;
int graph[MAX][MAX];
bool vist[MAX][MAX];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y, int height) // height : 수심의 높이
{
    vist[x][y] = true;
    int newX, newY;
    for (int i = 0; i < 4; i++)
    {
        newX = x + dx[i];
        newY = y + dy[i];
        if (1 <= newX && newX <= n && 1 <= newY && newY <= n)
        {
            if (vist[newX][newY] == false && graph[newX][newY] > height) // 물에 잠기지 않은 경우에만 탐색
            {
                dfs(newX, newY, height);
            }
        }
    }
}

int main()
{
    cin >> n;
    int max_height = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &graph[i][j]);
            if (max_height < graph[i][j])
            {
                max_height = graph[i][j];
            }
        }
    }
    int result = 0;
    for (int i = 0; i <= max_height; i++)
    {
        int count = 0;
        memset(vist, false, sizeof(vist));
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                if (vist[j][k] == false && graph[j][k] > i) //물에 잠기지 않은 경우만 탐색
                {
                    count++;
                    dfs(j, k, i);
                }
            }
        }
        result = max(result, count);
    }
    cout << result;
    return 0;
}