Analysis: Island Travels by Neal Wu

This problem is somewhat complex, and the algorithm to solve it uses the following three major steps:

1. Flood fill to find the islands. (Both depth-first search, DFS, and breadth-first search, BFS, will work fine here.)

2. Flood fill to find the distances between all pairs of islands. (BFS should be considerably faster than DFS here.)

3. After finding the distances between all pairs of islands, find the minimum distance needed to traverse all islands. (This is a well-known problem that is also known as the Traveling Salesman Problem.) The simplest solution to this would be to try all possible orderings of the islands, but this is far too slow for N = 15. To speed up the algorithm, we can use dynamic programming, with our state consisting of our current location and the subset of islands that we have visited, and the value as the current total distance. This algorithm can be implemented either recursively or iteratively for a complexity of O(N² x 2^N).

The following is a solution using this idea:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

FILE *fout = fopen ("island.out", "w");
FILE *fin = fopen ("island.in", "r");

const int INF = 1000000000;
const int dr [] = {-1, 0, 0, 1};
const int dc [] = {0, -1, 1, 0};

const int MAXN = 16;
const int MAXG = 55;
const int MAXS = 70000;

struct loc
{
    int row, col, dis;

    loc (int r, int c, int d)
    {
	row = r, col = c, dis = d;
    }
};

int N, R, C;

char grid [MAXG][MAXG];
int group [MAXG][MAXG];

int tdist [MAXG][MAXG];
int dist [MAXN][MAXN];
queue <loc> q;

int best [MAXN][MAXS];
int masks [MAXS];
int msize;

int ans;

inline bool comp (int a, int b)
{
    return __builtin_popcount (a) < __builtin_popcount (b);
}

void floodfill (int r, int c)
{
    group [r][c] = N;

    for (int k = 0; k < 4; k++)
    {
	int nr = r + dr [k];
	int nc = c + dc [k];

	if (grid [nr][nc] == 'X' && group [nr][nc] == -1)

	    floodfill (nr, nc);
    }
}

void solveislands ()
{
    memset (group, -1, sizeof (group));

    N = 0;

    for (int i = 1; i <= R; i++)
	for (int j = 1; j <= C; j++)
	    if (grid [i][j] == 'X' && group [i][j] == -1)
	    {
		floodfill (i, j);
		N++;
	    }
}

void solvedist ()
{
    memset (dist, 63, sizeof (dist));

    for (int i = 0; i < N; i++)
    {
	int ir = -1, ic = -1;
	bool found = false;

	for (int r = 1; r <= R && !found; r++)
	    for (int c = 1; c <= C && !found; c++)
		if (group [r][c] == i)
		{
		    ir = r, ic = c;
		    found = true;
		}


	memset (tdist, 63, sizeof (tdist));

	q.push (loc (ir, ic, 0));
	tdist [ir][ic] = 0;


	while (!q.empty ())
	{
	    loc top = q.front ();
	    q.pop ();


	    if (group [top.row][top.col] != -1)
	    {
		if (top.dis < dist [i][group [top.row][top.col]])
		    dist [i][group [top.row][top.col]] = top.dis;
	    }

	    for (int k = 0; k < 4; k++)
	    {
		int nr = top.row + dr [k];
		int nc = top.col + dc [k];

		if (grid [nr][nc] == 'X')
		{
		    if (top.dis < tdist [nr][nc])
		    {
			tdist [nr][nc] = top.dis;
			q.push (loc (nr, nc, top.dis));
		    }
		}
		else if (grid [nr][nc] == 'S')
		{
		    if (top.dis + 1 < tdist [nr][nc])
		    {
			tdist [nr][nc] = top.dis + 1;
			q.push (loc (nr, nc, top.dis + 1));
		    }
		}
	    }
	}
    }
}

void solvetsp ()
{
    memset (best, 63, sizeof (best));

    for (int i = 0; i < N; i++)
	best [i][1 << i] = 0;


    msize = 0;

    for (int m = 1; m < (1 << N); m++)
	masks [msize++] = m;

    sort (masks, masks + msize, comp);


    for (int ind = 0; ind < msize; ind++)
    {
	int m = masks [ind];

	for (int i = 0; i < N; i++)
	    if (best [i][m] < INF)
	    {
		for (int j = 0; j < N; j++)
		    if (best [i][m] + dist [i][j] < best [j][m | (1 << j)])
			best [j][m | (1 << j)] = best [i][m] + dist [i][j];
	    }
    }


    ans = INF;

    for (int i = 0; i < N; i++)
	if (best [i][(1 << N) - 1] < ans)
	    ans = best [i][(1 << N) - 1];
}

int main ()
{
    memset (grid, '.', sizeof (grid));

    fscanf (fin, "%d %d", &R, &C);

    for (int i = 1; i <= R; i++)
	fscanf (fin, "%s", &grid [i][1]);


    solveislands ();

    solvedist ();

    solvetsp ();


    fprintf (fout, "%d\n", (ans < INF) ? ans : -1);

    return 0;
}