[アルゴリズム]BOJ 14502(研究所)

ソース:https://www.acmicpc.net/problem/14502

質問する

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、1つの壁で構成され、壁は1つのスペースでいっぱいです.
一部の格子にはウイルスが存在し、このウイルスは上下左右に隣接する格子に伝播することができる.新しく立てた壁は3つあるので,3つ立てなければならない.
たとえば、研究所がある場合を見てみましょう.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

このとき、0はスペース、1は壁、2はウイルスがいる場所です.壁を立てなければ、ウイルスはすべてのスペースに拡散することができます.
2行1列、1行2列、4行6列に壁を設けると、地図の形は以下のようになります.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

ウイルスが拡散した様子は以下の通りです.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

3つの壁を設置した後、ウイルスが拡散できない場所を安全区域と呼ぶ.上の地図では、安全区域の大きさは27です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.

入力

第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目からN行目に地図の形状を与える.0はスペース、1は壁、2はウイルスの位置です.2の個数は2以上、10以下の自然数である.
スペースの数は3つ以上です.

しゅつりょく

最初の行で取得できるセキュリティ領域の最大サイズを出力します.

正しいコード

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int y,x,minV=1000000;

int dy[] = {-1, 1, 0, 0};
int dx[] = {0, 0, -1, 1};

int finderV(vector<vector<int>>& v, vector<vector<bool>> c)
{
    int ret=0;

    queue<pair<int,int>> q;

    for(int i=0; i<y; i++)
    {
        for(int j=0; j<x; j++)
        {
            if(v[i][j]==1 || v[i][j]==2)    c[i][j]=true;
            if(v[i][j]==2)
            {
                q.push({i,j});
                ret++;
            }
        }
    }

    while(!q.empty())
    {
        int posy = q.front().first;
        int posx = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++)
        {
            if(posy+dy[i]<y && posx+dx[i]<x && posy+dy[i]>=0 && posx+dx[i]>=0)
            {
                if(!c[posy+dy[i]][posx+dx[i]])
                {
                    c[posy+dy[i]][posx+dx[i]]=true;
                    q.push({posy+dy[i],posx+dx[i]});
                    ret++;
                }
            }
        }
    }

    return ret;
}

void makewall(int posy, int posx, int n, vector<vector<int>>& v, vector<vector<bool>>& c)
{
    if(n==3)
    {
        minV = min(minV, finderV(v,c));

        return;
    }

    for(int i=posy; i<y; i++)
    {
        for(int j=posx; j<x; j++)
        {
            if(!c[i][j])
            {
                c[i][j]=true;
                makewall(i,j,n+1, v, c);
                c[i][j]=false;
            }
        }
        posx=0;
    }

    return;
}

int main()
{
    int wallcnt=0;

    cin >> y >> x;

    vector<vector<int>> v(y,vector<int> (x,0));
    vector<vector<bool>> check(y,vector<bool> (x,false));

    for(int i=0; i<y; i++)
    {
        for(int j=0; j<x; j++)
        {
            cin >> v[i][j];
            if(v[i][j]==1 || v[i][j]==2)    check[i][j]=true;
            if(v[i][j]==1)  wallcnt++;
        }
    }

    makewall(0,0,0,v,check);

    cout << x*y-wallcnt-3-minV;

    return 0;
}

解答と思考過程

この問題は同時に解決した2つの問題である.

3種(3面壁)組合せ

bfs

この二つのことは同時にしなければならない.
複雑に見えますが、順番に解決すればいいので難しくはありません.makewall関数で壁を作成する重複文に問題が発生しました.
最初の繰り返し文から終了すると、posx=0posxが常に右端配列のみを示す場合、これは完全に検出できない.
この部分で長い間うろうろしていたが、最後に解決を求めた.