题目
Hearing that the latest fashion trend was cows with three spots on their hides, Farmer John has purchased an entire herd of three-spot cows. Unfortunately, fashion trends tend to change quickly, and the most popular current fashion is cows with only one spot!
FJ wants to make his herd more fashionable by painting each of his cows in such a way that merges their three spots into one. The hide of a cow is represented by an N by M grid of characters like this:
Here, each ‘X’ denotes part of a spot. Two 'X’s belong to the same spot if they are vertically or horizontally adjacent (diagonally adjacent does not count), so the figure above has exactly three spots. All of the cows in FJ’s herd have exactly three spots.
FJ wants to use as little paint as possible to merge the three spots into one. In the example above, he can do this by painting only four additional characters with 'X’s (the new characters are marked with '*'s
below to make them easier to see).
Please help FJ determine the minimum number of new 'X’s he must paint in order to merge three spots into one large spot.
输入
- Line 1: Two space-separated integers, N and M (1 <= N,M <= 50).
- Lines 2…1+N: Each line contains a length-M string of 'X’s and ‘.’ specifying one row of the cow hide pattern.
输出
- Line 1: The minimum number of new 'X’s that must be added to the input pattern in order to obtain one single spot.
样例输入
样例输出
3
题目大意：
三个由X形成的连通块，将最少的.改为*使得三个连通块连在一起。
题解：
分两种情况，
一种是算两两距离，然后三个选两个求最小
一种是求一个点，三个连通块到这个点距离最小
两种情况取min
代码：
//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define rep(i,a,b) for(auto i = (a);i<=(b);i++)
#define dep(i,a,b) for(auto i = (a);i>=(b);i--)
using namespace std;
typedef long long ll;
bool flag;
char mp[110][110];
ll n,m;
ll cnt=1;
ll col[110][110];
void dfs(ll x,ll y)
{
ll dx[4]={0,0,1,-1};
ll dy[4]={1,-1,0,0};
if(mp[x][y]!='X'||col[x][y])return;
flag=1;
col[x][y]=cnt;
rep(i,0,3)
{
ll nx=dx[i]+x;
ll ny=dy[i]+y;
if(nx<1||nx>n||ny<1||ny>m)continue;
dfs(nx,ny);
}
}
ll dis[10][110][110];
void qdis(ll x,ll y)
{
rep(i,1,n)rep(j,1,m)if(col[i][j]!=col[x][y])
dis[col[x][y]][i][j]=min(dis[col[x][y]][i][j],max(0ll,abs(x-i)+abs(y-j)-1));
}
ll find_ans(ll a,ll b)
{
ll re=0x3f3f3f3f;
rep(i,1,n)rep(j,1,m)
if(col[i][j]==b)
re=min(re,dis[a][i][j]);
return re;
}
void AC()
{
memset(dis,0x3f3f3f3f,sizeof dis);
cin>>n>>m;
rep(i,1,n)rep(j,1,m) cin>>mp[i][j];
rep(i,1,n)rep(j,1,m){
flag=0;
dfs(i,j);
if(flag)cnt++;
}
//染色
//每个连通块到每个点的距离
rep(i,1,n)rep(j,1,m)qdis(i,j);
ll ans=10000000000000;
rep(i,1,n)
rep(j,1,m)
rep(k,1,3)
if(dis[k][i][j]>=0x3f3f3f3f)dis[k][i][j]=0;
rep(i,1,n)
rep(j,1,m)
if(!col[i][j])
ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]+1);
else
ans=min(ans,dis[1][i][j]+dis[2][i][j]+dis[3][i][j]);
ll ans12=find_ans(1,2);
ll ans13=find_ans(1,3);
ll ans23=find_ans(2,3);
ans=min(ans,min(ans12+ans13,min(ans12+ans23,ans13+ans23)));
cout<<ans<<endl;
}
int main()
{
int _=1;
while(_--)AC();
return 0;
}
//附赠几个具有代表性的数据
/*
5 5
..X..
.....
.....
.....
X...X
答案为6
*/
/*
6 5
X....
.....
.....
.....
.X...
XX..X
答案为6
*/
/*
2 3
.X.
X.X
答案为1
*/