天下一プログラマコンテスト2012 予選B D - 大爆発

大爆発

爆弾を置くy座標を決める（同じy座標に複数の爆弾を置くのもあり）と、そのように爆弾を置いて全ての壁を破壊するのに必要な爆弾の個数が求められる。そのy座標に空きが無ければ無理。それ以外の場合は、そのy座標以外にある壁を壊すのに爆弾が何個必要かを考える。あるマス(x,y)が最初から空きならy行目とx列目を同時に破壊できる。壁なら、y行目とx列目を破壊するのに別々に爆弾が必要になる。y行目とx列目を同時に破壊する爆弾の割り当ては、最大二部マッチングを用いる。

↓時間制限3000msのところを、2986msで通ったコード。配列を最初に確保しておけば、もう少し速くなると思う。

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>

using namespace std;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

//  最大流
int maxflow( vector<vector<int> > edge, int s=0, int t=-1 )
{
    int n = (int)edge.size();
    if ( t<0 )  t = n-1;
    int f = 0;
    vector<vector<int> > F(n,vector<int>(n));
    while(true)
    {
        vector<int> P(n,-1);  P[s]=-2;
        vector<int> Q(1,s);
        while ( !Q.empty() && P[t]==-1 )
        {
            int u = Q.back();  Q.pop_back();
            for ( int v=0; v<n && P[t]==-1; v++ )
            if ( P[v]==-1 && edge[u][v]-F[u][v]>0 )
                P[v] = u,
                Q.push_back(v);
        }
        if ( P[t]==-1 )  break;

        int m = edge[P[t]][t];
        for ( int v=P[t]; v!=s; v=P[v] )
            m = min(m,edge[P[v]][v]-F[P[v]][v]);

        f += m;
        for ( int v=t; v!=s; v=P[v] )
            F[P[v]][v] += m,
            F[v][P[v]] -= m;
    }

    return f;
}

//  二部グラフの最大マッチング
int bipartite( vector<vector<bool> > edge )
{
    int n = (int)edge.size();
    int m = (int)edge[0].size();
    vector<vector<int> > E(n+m+2,vector<int>(n+m+2));

    for ( int i=0; i<n; i++ )
        E[0][i+1] = 1;
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<m; j++ )
        if ( edge[i][j] )
            E[i+1][j+n+1] = 1;
    for ( int i=0; i<m; i++ )
        E[i+n+1][n+m+1] = 1;

    return maxflow(E);
}

int main()
{
    int H,W;
    cin>>H>>W;
    vector<string> c(H);
    for ( int y=0; y<H; y++ )
        cin>>c[y];

    bool emp = true;
    for ( int y=0; y<H; y++ )
    for ( int x=0; x<W; x++ )
        if ( c[y][x]=='#' )
            emp = false;
    if ( emp )
    {
        cout << 0 << endl;
        return 0;
    }

    int ans = 99999999;

    for ( int b=1; b<(1<<H); b++ )
    {
        bool ok = false;
        int remain = 0;

        for ( int y=0; y<H; y++ )
        for ( int x=0; x<W; x++ )
        {
            if ( (b>>y&1) && c[y][x]=='.' )
                ok = true;
            if ( !(b>>y&1) && c[y][x]=='#' )
                remain |= 1<<x;
        }

        if ( !ok )
            continue;

        vector<vector<bool> > E(H,vector<bool>(W));
        for ( int y=0; y<H; y++ )
        for ( int x=0; x<W; x++ )
            E[y][x] = ( c[y][x]=='.' && (b>>y&1) && (remain>>x&1) );

        int n = bipartite(E);

        ans = min( ans, countbit(b)+countbit(remain)-n );
    }
    
    cout << (ans<99999999?ans:-1) << endl;

    return 0;
}