Poj Solution 2711

http://poj.org/problem?id=2711

#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define min(a,b) (((a)<(b))?(a):(b))

using namespace std;

class ff
{

public:    
    typedef int type;            // ��Ȩ����
    enum { size = 810 };        // �����ģ
    enum { max = ( 1<<30 ) };    // �����������

    //    ��ʼ��
    void init();

    //    ����һ��� from �� to ��������Ϊ limit �������
    void insert_edge( int from, int to, type limit );

    //    ����n����ͼ�У��� ����s �� ����t �������
    type maxflow( int n, int s, int t );

private:

    struct edge
    {
        int to;        // �ñ�ָ��Ķ�
        type c, f;  // ��������
        int rev_i;  // e[to][rev_i] Ϊ�ñߵ������
    };//�ߵ�����

    typedef vector<edge> set_edge;  // �ߵļ�������

    set_edge e[size]; // ��
    bool sign[size];  // ���ʱ�־
    
    void add_flow( edge &ee, type d );        // ��ӱߵ���
    type search( int k, int t, int best );  // ��������ع첢����
};

/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//    ������


void ff::init()
{
    int i;
    for( i=0; i<size; i++ )
        e[i].clear();
}
void ff::insert_edge( int from, int to, type limit )
{
    edge e1 = { to, limit, 0, e[to].size() }, e2 = { from, 0, 0, e[from].size() };

    e[ from ].push_back( e1 );
    e[ to ].push_back( e2 );
}

void ff::add_flow( edge &ee, type d )
{
    ee.f += d;
    e[ ee.to ][ ee.rev_i ].f -= d;
}

ff::type ff::search( int k, int t, int best )
{
    int i, m = e[k].size();

    type temp;
    edge *ep;

    sign[k] = true;

    if( k == t )
        return best;

    for( i=0; i<m; i++ )
    {
        ep = &e[k][i];
        if( ep->f < ep->c && !sign[ ep->to ] )
        {
            if( ( temp = search( ep->to, t, min( best, ep->c - ep->f ) ) ) > 0 )
            {
                ep->f += temp;
                e[ ep->to ][ ep->rev_i ].f -= temp;
                return temp;
            }
        }
    }
    return 0;
}

ff::type ff::maxflow( int n, int s, int t )
{
    type total = 0, add = 0;

    do
    {
        total += add;
        memset( sign, 0, n );
    }
    while( ( add = search( s, t, max ) ) > 0 );

    return total;
}

/****************************************************************************/
char map[20][25];
char at[20][25];
int n, m, d, begin, end, total;
ff mf;

void init()
{
    int i, j, k, l;
    scanf( "%d %d", &n, &d );
    
    for( i=0; i<n; i++ )
        scanf( "%s", map[i] );
    for( i=0; i<n; i++ )
        scanf( "%s", at[i] );
        
     m = strlen( map[0] );
     
     mf.init();
     
     for( i=0; i<n; i++ )
     for( j=0; j<m; j++ )
        if( map[i][j] > '0' )
            mf.insert_edge( i*m+j, i*m+j+n*m, map[i][j] -'0' );
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    if( map[i][j] >'0' )
    for( k=(i-d>0)?i-d:0; k<=i+d&&k<n; k++ )
    for( l=(j-d>0)?j-d:0; l<=j+d&&l<m; l++ )
        if( map[k][l] > '0' && abs( i-k ) + abs( j-l ) <= d )
            mf.insert_edge( i*m+j+n*m, k*m+l, map[k][l] - '0' );

    begin = n*m*2;
    end = n*m*2+1;
    total = 0;
    
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
        if( at[i][j] == 'L' )
        {
              mf.insert_edge( begin, i*m+j, 1 );
              total++;
        }          
            
    for( i=0; i<n; i++ )
    for( j=0; j<m; j++ )
    if( map[i][j] > '0' )        
          if( i-d<0 || i+d >= n || j-d<0 || j+d >= m )
            mf.insert_edge( i*m+j+n*m, end, map[i][j] - '0' );
}

int main()
{
    int cas, ans, i;
    
    scanf( "%d", &cas );
    
    for( i=1; i<=cas; i++ )
    {
        init();
        ans = total - mf.maxflow( n*m*2+2, begin, end );
        
        printf( "Case #%d: ", i );
        
        if( ans == 0 )
            printf( "no lizard was left behind.n" );
        else if( ans == 1 )
            printf( "1 lizard was left behind.n" );
        else
              printf( "%d lizards were left behind.n", ans );
     }             
    return 0;
}