暴搜 - 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 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;

                   }

               }

           }

               pair<int, int> now = Q.front();

               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;

               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;

}