Solution Notes: This was by far the most challenging problem on the bronze contest. To solve it, we first label each of the two spots by using the recursive "flood fill" function label() that spreads out and sets every character in the spot to 1 (for the first spot) or 2 (for the second spot). This recursive function is first called when we see an 'X', after which it labels the spot containing that 'X' with 1s; it then continues scanning until it finds another 'X', after which it is called to label the spot containing that 'X' with 2s. Each time label() is called, it marks a single character and then recursively tries to visit the neighbors of that character, stopping any time we land on a character that isn't 'X'. One concern with this approach is sometimes that if the input grid is large enough, then we may run out of stack space if the label() function recurses too deeply. Fortunately, the grid here is small enough that this is not a concern (if you want to be particularly careful about this issue, you can explicitly allocate and manage the stack of recursive locations to visit, although this is a bit more code).

Once our spots are labeled, we want to find the '1' character and the '2' character that are closest together (i.e., the two characters that we need to join with a path to merge the two spots). Distance here is measured by taking the sum of absolute difference in coordinates - this is sometimes called "Manhattan" or "L1" distance. Since the grid is small enough, we can simply loop over all possible pairs of '1' characters and '2' characters and test the distance between each. If the grid was much larger, we would need to use slightly more sophisticated techniques, such as for example a breadth-first search (which is more of a silver-level technique) to quickly compute the shortest path distance from every character in the grid to a spot.

#include <stdio.h>
#define MAX_N 50
#define MAX_M 50

char G[MAX_N][MAX_M+1];
int N, M;

int label(int r, int c, char ch)
{
  if (G[r][c]!='X') return;
  G[r][c] = ch;
  if (r>0) label(r-1,c,ch);
  if (c>0) label(r,c-1,ch);
  if (r<N-1) label(r+1,c,ch);
  if (c<M-1) label(r,c+1,ch);
}

int abs(x)
{
  if (x>=0) return x;
  return -x;
}

int mindist(void)
{
  int r1, r2, c1, c2, min=MAX_N+MAX_M;
  
  for (r1=0; r1<N; r1++)
    for (c1=0; c1<M; c1++)
      if (G[r1][c1]=='1')
	for (r2=0; r2<N; r2++)
	  for (c2=0; c2<M; c2++)
	    if (G[r2][c2]=='2')
	      if (abs(r1-r2) + abs(c1-c2) < min)
		min = abs(r1-r2) + abs(c1-c2);
  return min - 1;
}

int main(void)
{
  int r, c;
  char ch='0';

  freopen ("pageant.in", "r", stdin);
  freopen ("pageant.out", "w", stdout);

  scanf ("%d %d", &N, &M);
  for (r=0; r<N; r++)
    scanf ("%s", &G[r]);

  for (r=0; r<N; r++)
    for (c=0; c<M; c++)
      if (G[r][c] == 'X') 
	label(r,c,++ch);
  
  printf ("%d\n", mindist());
  return 0;
}