暴搜 - Codeforces Round #327 (Div. 2) E. Three States

 E. Three States 

Problem's Link

---

 

Mean: 

在一个N*M的方格内，有五种字符：'1','2','3','.','#'.

现在要你在'.'的地方修路，使得至少存在一个块'1','2'和'3'是连通的.

问：最少需要修多少个'.'的路.

analyse:

想法题，想到了就很简单.

直接暴力枚举每个国家到每个可达的点的最小代价，然后计算总和取最小值.

dis[k][x][y]表示第k个国家到达坐标(x,y)的点的最小代价.

Time complexity: O(N)

 

view code

/*
* -----------------------------------------------------------------
* Copyright (c) 2015 crazyacking All rights reserved.
* -----------------------------------------------------------------
*       Author: crazyacking
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);

const int MAXN = 1001;
char s [ MAXN ][ MAXN ];
int dx [ 4 ] = { - 1 , 0 , 1 , 0 };
int dy [ 4 ] = { 0 , - 1 , 0 , 1 };
int dis [ 3 ][ MAXN ][ MAXN ];
int main()
{
    ios_base :: sync_with_stdio( false);
    cin . tie( 0);
    int n , m;
    while ( ~ scanf( "%d %d" , &n , & m))
    {
        for ( int i = 0; i < n; ++ i)
            scanf( "%s" , s [ i ]);
        for ( int i = 0; i < n; ++ i)
            for ( int j = 0; j < m; ++ j)
                dis [ 0 ][ i ][ j ] = dis [ 1 ][ i ][ j ] = dis [ 2 ][ i ][ j ] = ( int) 1e8;
        queue < pair < int , int > > Q;
        for ( int k = 0; k < 3; ++ k)
        {
            while ( ! Q . empty())
                Q . pop();
            for ( int i = 0; i < n; ++ i)
            {
                for ( int j = 0; j < m; ++ j)
                {
                    if (s [ i ][ j ] == k + '1')
                    {
                        Q . push( make_pair( i , j));
                        dis [ k ][ i ][ j ] = 0;
                    }
                }
            }

            while ( ! Q . empty())
            {
                pair < int , int > now = Q . front();
                Q . pop();
                int x = now . first;
                int y = now . second;
                for ( int i = 0; i < 4; ++ i)
                {
                    int xx = x + dx [ i ];
                    int yy = y + dy [ i ];
                    if ( !( xx >= 0 && xx < n)) continue;
                    if ( !( yy >= 0 && yy < m)) continue;
                    if (s [ xx ][ yy ] == '#') continue;
                    if ( dis [ k ][ xx ][ yy ] > dis [ k ][ x ][ y ] + (s [ x ][ y ] == '.'))
                    {
                        dis [ k ][ xx ][ yy ] = dis [ k ][ x ][ y ] + (s [ x ][ y ] == '.');
                        Q . push( make_pair( xx , yy));
                    }
                }
            }
        }
        int ans = 1e9;
        for ( int i = 0; i < n; ++ i)
        {
            for ( int j = 0; j < m; ++ j)
                ans = min( ans , dis [ 0 ][ i ][ j ] + dis [ 1 ][ i ][ j ] + dis [ 2 ][ i ][ j ] +(s [ i ][ j ] == '.'));
        }
        if ( ans >= 1e8)
            puts( "-1");
        else
            printf( "%d \n " , ans);
    }
    return 0;
}
/*

*/