SPOJ LABYR1

From Algorithmist
Jump to navigation Jump to search

38 - Labyrinth[edit]

http://spoj.sphere.pl/problems/LABYR1/

Summary[edit]

This problem essentially requires us to calculate the longest path from one end of the labyrinth to another end. One essential observation to make is that the constraints on the problem hint out that the layout of the labyrinth is a tree. In Graph Theory terms, the problem asks us to find the diameter of the underlying tree.

Explanation[edit]

We need to make several observations, firstly the underlying layout of the labyrinth is a tree. Secondly, we need some method of traversing or visiting each cell of the labyrinth. Finally, we also need a way to know we are a "leaf" of the tree, i.e. a cell that is the start/end of a maximal path. Firstly the statement, "The labyrinth is designed in such a way that there is exactly one path between any two free blocks" hints that it's a tree by the definition of a tree. Secondly the method we traverse the labyrinth is probably most suited to a Depth First Search (DFS) although a BFS should also work. The only thing we really need to keep track of in the DFS is the distance from the starting node. The main idea is to choose a specific node that guarantees that a traversal of a DFS to all other nodes will yield a maximum length (i.e. choose the node that is an end-point of the diameter). How can we find such a node? Firstly, we start at any leaf in the tree, a good and natural choice would be the upper left-most free block. We proceed to do a DFS on this node, from this we get the node that is the furthest away from our initial leaf. This node should also be a leaf on the tree (convince yourself by drawing diagrams), then we do another DFS starting from our new node, and the diameter of the tree is simply the largest distance obtained by this DFS.

Implementation/Hints[edit]

The DFS used in this problem is standard, the only extra work it needs to do is to keep track of the distance from the starting node. This can be done by adding the distance by 1 for every depth we traverse and simply choosing the maximum depth for all the traversals we do recursively. The following code template outlines that approach:

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int dfs(int x, int y) {
	if (visited[x][y]) return 0;
	visited[x][y] = true;
	int best = 0;
	for (int i = 0; i < 4; i++) {
		int modx = dx[i]+x; int mody = dy[i]+y;
		if (adjmat[modx][mody] > 0) {
			int v = dfs(modx,mody);
			if (v > best) {
				best = v;
			}
		}
	}
	return best+1;
}

We also need to keep track of the "coordinates" that the best DFS ends with because these are used for subsequent DFS calls. You can accomplish this via the addition of several variables:

int newX, newY;

int dfs(int x, int y) {
	if (visited[x][y]) return 0;
	visited[x][y] = true;
	int best = 0;
        int bestX = x, bestY = y;
	for (int i = 0; i < 4; i++) {
		int modx = dx[i]+x; int mody = dy[i]+y;
		if (adjmat[modx][mody] > 0) {
			int v = dfs(modx,mody);
			if (v > best) {
				best = v;
                                bestX = newX; bestY = newY;
			}
		}
                newX = bestX; newY = bestY;
	}
	return best+1;
}

Here there are global variables of newX and newY which are the coordinates which yield the largest distance, these are used for subsequent calls. The local variables of bestX and bestY are used as temporary variables which hold the best coordinates for a specific traversal from a node.

Input[edit]

2
3 3
###
#.#
###
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######

Output[edit]

Maximum rope length is 0.
Maximum rope length is 8.