Solution Notes: We first use a recursive "floodfill" to label the characters in the three different spots with 1s, 2s, and 3s (in the process, we may also want to make a list of the locations of the characters in each spot). Next, we need to figure out the optimal way to join the three spots together. There are two possible ways to do this, and we must try both and take whichever yields the best solution: (1) pick one character, and draw shortest paths from this character outward to each of the three spots, or (2) find the shortest paths joining spots 1+2, 1+3, and 2+3, and take the smallest two of these. Here, a "shortest path" means a path whose "Manhattan" length (sum of absolute differences in coordinates) in smallest. There are several ways we can test all solutions of types (1) and (2) efficiently. Since the grid size is small enough, we can actually get away with more or less brute-force enumeration and still run in time; for example, we can loop over every pair of characters (2500^2 choices), in order to check all the shortest path distances we need. If the grid was much larger, we would probably need to use a breadth-first search in both cases to reduce the total shortest path computation time to linear in the total size of the grid, rather than quadratic in the size of the grid.

``````

#include <stdio.h>
#include <stdlib.h>
char cow[50][50];
int N, M, spots[3][2500][2], counts[3];

void mark_spot(int a, int b, int num) {
if(a<0 || b<0 || a==N || b==M || cow[a][b]!='X') return;
cow[a][b] = 'V';
spots[num][counts[num]][0] = a;
spots[num][counts[num]++][1] = b;
mark_spot(a-1, b, num);
mark_spot(a+1, b, num);
mark_spot(a, b-1, num);
mark_spot(a, b+1, num);
}

int l1_dist(int a1, int b1, int a2, int b2) {
return abs(a1-a2)+abs(b1-b2);
}

int try_point(int a, int b) {
if(cow[a][b]=='V') return 1000;
int i, j, ans = 0;
for(i=0; i<3; i++) {
int min = 101;
for(j=0; j<counts[i]; j++) {
int t = l1_dist(spots[i][j][0], spots[i][j][1], a, b)-1;
if(t<min) min = t;
}
ans+=min;
}
return ans+1;
}

int main() {
freopen("pageant.in", "r", stdin); freopen("pageant.out", "w", stdout);
scanf("%d %d", &N, &M);
int i, min = 301, j, num_spots = 0, mins[3], k;

for(i=0; i<N; i++)
scanf("%s", cow[i]);

for(i=0; i<N; i++)
for(j=0; j<M; j++)
if(cow[i][j]=='X')
mark_spot(i,j,num_spots++);

for(i=0; i<N; i++)
for(j=0; j<M; j++) {
int t = try_point(i,j);
if(t<min) min = t;
}

for(i=0; i<3; i++) {
mins[i]=101;
for(j=0; j<counts[i]; j++)
for(k=0; k<counts[(i+1)%3]; k++) {
int t = l1_dist(spots[i][j][0], spots[i][j][1], spots[(i+1)%3][k][0], spots[(i+1)%3][k][1])-1;
if(t<mins[i]) mins[i] = t;
}
}

for(i=0; i<3; i++)
if(mins[i]+mins[(i+1)%3]<min)
min = mins[i]+mins[(i+1)%3];

printf("%d\n", min);

return 0;
}
``````