Original address: http://www.usaco.org/index.php?page=viewproblem2&cpid=87
Title Description
Hearing that the latest fashion trend was cows with two spots on their hides, Farmer John has purchased an entire herd of two-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 two spots into one. The hide of a cow is represented by an N by M (1 <= N,M <= 50) grid of characters like this:
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....
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 two spots. All of the cows in FJ's herd have exactly two spots.
FJ wants to use as little paint as possible to merge the two spots into one. In the example above, he can do this by painting only three
additional characters with 'X's (the new characters are marked with '*'s below to make them easier to see).
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX....
Please help FJ determine the minimum number of new 'X's he must paint in order to merge two spots into one large spot.
It is said that the recent popular trend is cows with two spots on the cow leather. Farmer John bought a whole group of cows with two spots.
Unfortunately, fashion trends tend to change rapidly. At present, the most popular fashion is the cow with only one spot!
FJ wants to use the painting method to connect the two spots of each of his cows into one spot, so as to make his cattle more fashionable. The cow's skin is represented by a character grid of n*m (1 < = n, m < = 50):
................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....
Here, each 'X' represents a part of a spot. Two 'X' vertically or horizontally adjacent (diagonal adjacent not included) belong to the same spot, so there are exactly two spots in the above figure. All FJ cows have exactly two spots.
FJ wants to combine two spots into one with as little paint as possible. In the above example, he can do this by drawing three additional characters.
The additional character "X" (the new character is represented as * in the figure below, which is easy to see).
................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ........XXXXX... .........XXX....
Please help FJ determine the minimum number of painted points so that the two spots can be combined into one.
input
* Line 1: Two space-separated integers, N and M.
* Lines 2...1+N: Each line contains a length-M string of 'X's and '.'s specifying one row of the cow hide pattern.
Line 1: an integer separated by two spaces, N and M.
Line 2... 1+N: each line contains a string of length M, only 'X' and '.' Composition, representing the animal skin pattern of a cow.
output
* Line 1: The minimum number of new 'X's that must be added to the input pattern in order to obtain one single spot.
Line 1: add the minimum number of new 'X' characters so that the two spots can be combined into a single spot.
Sample
input
6 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... .........XXX....
output
3
Tips
INPUT DETAILS:
The pattern in the input shows a cow hide with two distinct spots, labeled 1 and 2 below:
................ ..1111....222... ...1111....22... .1111......222.. ........22222... .........222....
OUTPUT DETAILS:
Three 'X's suffice to join the two spots into one:
................ ..1111....222... ...1111X...22... .1111..XX..222.. ........22222... .........222....
Enter Description:
The input cow skin pattern has two obvious spots, which are represented by label 1 and label 2 respectively as follows:
................ ..1111....222... ...1111....22... .1111......222.. ........22222... .........222....
Output Description:
Three 'X's are enough to turn two spots into one.
................ ..1111....222... ...1111X...22... .1111..XX..222.. ........22222... .........222....
Meaning:
There are two connected blocks in a graph. Find out how many points need to be filled to connect the two connected blocks together.
Idea:
One of the connected blocks is traversed by dfs and marked to distinguish the two connected blocks.
Store two connected blocks respectively according to the mark.
Find the Manhattan distance (violence cycle) between the points belonging to two connected blocks, and take the minimum value.
AC Code:
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define map Map
int n,m;
int map[57][57];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void init(){//Save map
char c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='X')map[i][j]=1;
}
}
}
void dfs(int x,int y){//Traverse 1 connected block
map[x][y]=2;//Mark
for(int i=0;i<4;i++){
if(map[ x+dx[i] ][ y+dy[i] ]==1){
dfs(x+dx[i],y+dy[i]);
}
}
}
struct node{
int x,y;
};
node pot1[2500],pot2[2500];//Two connected blocks
int p1,p2;
void savepot(){//Two connected blocks are stored respectively
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(map[i][j]==2){
pot1[p1]={i,j};
p1++;
}
else if(map[i][j]==1){
pot2[p2]={i,j};
p2++;
}
}
}
}
int mht(){//Find the Manhattan distance between two groups of points and take the minimum value
int min0=101,mht0;
for(int i=0;i<p1;i++){
for(int j=0;j<p2;j++){
mht0=abs(pot1[i].x-pot2[j].x)+abs(pot1[i].y-pot2[j].y)-1;
min0=min(mht0,min0);
}
}
return min0;
}
node first;
void findfirst(){//Find any point as the starting point of dfs
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(map[i][j]==1){
first={i,j};
return;
}
}
}
}
int main(){
cin>>n>>m;
init();
findfirst();
dfs(first.x,first.y);
savepot();
int ans=mht();
cout<<ans;
return 0;
}