暴搜

 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 ", ans);
   }
   return 0;
}
/*

*/