Problema de Novembro de 2004: Number Maze

Este mês proponho um problema que apareceu na 2ª prova de 2003 do Concurso de Programação ACM da Universidade do Porto. É o problema A, "Number Maze" e é também o problema que é referido no capítulo 4 da página de introdução. A solução não é trivial e podem usar como teste de input este ficheiro: ch4_4.txt (tem de acrescentar uma linha ao início com um "1" para funcionar!). Este input não serve tanto para testar a validez (para isso usem o input de exemplo) mas a eficiência; se o programa levar mais de 3 segundos para resolver este input, então é melhor tentar outra vez :)

Consider a number maze represented as a two dimensional array of numbers comprehended between 0 and 9, as exemplified below. The maze can be traversed following any orthogonal direction (i.e., north, south, east and west). Considering that each cell represents a cost, then finding the minimum cost to travel the maze from one entry point to an exit point may pose you a reasonable challenge.

Problem

Your task is to find the minimum cost value to go from the top-left corner to the bottom-right corner of a given number maze of size NxM where 1 <= N, M <= 999. Note that the solution for the given example is 24.

Input

The input file contains several mazes. The first input line contains a positive integer defining the number of mazes that follow. Each maze is defined by: one line with the number of rows, N; one line with the number of columns, M; and N lines, one per each row of the maze, containing the maze numbers separated by spaces.

Output

For each maze, output one line with the required minimum value.

Sample Input

2
4
5
0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
1
6
0 1 2 3 4 5

Sample Output

24
15

Um exemplo para explicar melhor:

1	9	9
1	9	9
1	1	1

É fácil de ver que a solução é 5, seguindo o caminho dos 1s. O algoritmo de procura exaustiva do capítulo 4 experimenta todos os caminhos, mesmo depois de ter percorrido o dos 1s. Vamos supor que o algoritmo avança nas casas na ordem baixo, direita, cima, esquerda. Então o primeiro caminho percorrido é o dos 1s. Quando volta da casa final (3,3), estamos outra vez na casa (3,2). O próximo passo é por isso ir para cima, para a casa (2,2). O algoritmo continua cegamente por todas as casas disponíveis até esgotar todas as possibilidades, apesar do custo acumulado ser maior do que uma solução temporária já descoberta: quando entramos na casa (2,2) o custo acumulado é 1+1+1+1+9 = 13, quando já tínhamos uma solução com custo 5. Por isso, seja qual for o percurso a partir desta casa, nunca vai chegar a uma solução melhor. O algoritmo de Dijkstra tira partido deste conhecimento.

Para ilustrar a ideia, vamos ver como o algoritmo resolvia este problema. De cada casa, o algoritmo avança para todas as direcções. Estas posições são guardadas num "map" (uma árvore binária balanceada), indexadas pelo custo acumulado. Isto é muito importante, porque permite saber imediatamente qual é o melhor caminho de entre os que estão guardados: é o primeiro da árvore (o elemento mais à esquerda). Para começar, metemos na árvore uma única posição que é a inicial, com custo acumulado 1. As posições que entraram estão a negrito e a que sai é sempre a que está à frente (porque tem menor custo):

1: (1,1)

2:  (2,1)
10: (1,2)

3:  (3,1)
10: (1,2)
11: (2,2)

4:  (3,2)
10: (1,2)
11: (2,2)

5:  (3,3)
10: (1,2)
11: (2,2)

Vamos analisar um exemplo mais elaborado, e ver os passos seguidos pelo algoritmo. Consideremos agora a matriz

1	2	0
1	2	9
2	9	0

Neste caso o algoritmo não vai fazer um caminho directo, mas vai saltar entre várias alternativas. No máximo, percorre todas as casas mas apenas uma vez. A solução é 12, que é fazer o caminho azul. No primeiro passo fica:

1: (1,1)

2: (2,1)
3: (1,2)

3: (1,2)
4: (2,2)
4: (3,1)

3: (1,3)
4: (2,2)
4: (3,1)

4:  (2,2)
4:  (3,1)
12: (2,3)

4:  (3,1)
12: (2,3)
13: (3,2)

12: (2,3)
13: (3,2)

O código seguinte é da autoria do Hugo Santos, com algumas modificações mínimas. Um input de uma matriz 1000x1000 para testar (2MB! Comprimido 8 KB): 2004nov.txt.gz. Código em C++:

#include <iostream>
#include <map>

struct Point {
	int x, y;
};

using namespace std;

#define maze(x,y) mazeptr[x + y*cols]
#define stepped(x,y) steppedptr[x + y*cols]

int *mazeptr;
bool *steppedptr;
int rows, cols;

multimap<int, Point> cost_map;
multimap<int, Point>::iterator cost_map_iter;

int dirs[4][2] = {
	{ -1,  0 }, // left
	{  0, -1 }, // up
	{  1,  0 },   // right
	{  0,  1 }     // down
	
};

bool valid(Point &p)
{
	return (p.x >= 0 && p.x < cols && p.y >= 0 && p.y < rows);
}

int cost()
{
	int i;
	int total;
	Point cur, p;

	cur.x = cur.y = 0;
	total = maze(cur.x, cur.y);
	cost_map.insert(pair<int, Point>(total, cur));

	for (;;) {
		cost_map_iter = cost_map.begin();
		cur = cost_map_iter->second;		
		total = cost_map_iter->first;

		for (i = 0; i < 4; i++) {
			p.x = cur.x + dirs[i][0];
			p.y = cur.y + dirs[i][1];
			if (p.x == cols - 1 && p.y == rows - 1)
				return total + maze(p.x, p.y);
			if (valid(p) && !stepped(p.x, p.y)) {
				cost_map.insert(pair<int, Point>(total + maze(p.x, p.y), p));
			}
		}

		cost_map.erase(cost_map_iter);
		stepped(cur.x, cur.y) = true;
	}
}

int main(int argc, char *argv[])
{
	int num_mazes, i, j;
	
	cin >> num_mazes;

	while (num_mazes--) {
		cin >> rows >> cols;
		mazeptr = new int[rows * cols];
		steppedptr = new bool[rows * cols];

		for (i = 0; i < rows; i++)
			for (j = 0; j < cols; j++) {
				cin >> maze(j, i);
				stepped(j,i) = false;
			}

		cout << cost() << endl;

		delete mazeptr;
		delete steppedptr;
	}
	
	return 0;
}

Comecemos por analisar a função main. O enunciado diz que o primeiro número no input é o número de problemas a resolver, e temos um ciclo que executa esse número de vezes (o ciclo while). Depois, criamos uma matriz que vai ter os custos e outra que diz se uma casa já foi visitada ou não. Continuamos com a leitura do input, inserindo o custo da casa respectiva na matriz e assinalando-a como não vizitada (valor lógico "false"). A função cost calcula o resultado que é depois enviado para a saída.

As matrizes usadas são representadas por um array; para indexar uma posição (x,y), usamos a posição (x + y*cols) do array. Para o código ficar mais claro, foram definidas as macros maze(x,y) e stepped(x,y), que indexam cada uma um dos arrays. A matriz dirs contém os incrementos que são feitos nas coordenadas (x,y) quando se anda para cima, baixo, esquerda ou direita. A função valid verifica se um ponto é válido, isto é, se as suas coordenadas são válidas (ficam dentro da matriz). O cost_map é a estrutura central: é onde são mapeados os custos em posições. É usado um multimap porque podem haver várias casas com o mesmo custo (num map normal, cada elemento tem de ter uma chave de indexação única; como a chave aqui são os custos e podem haver várias casas com o mesmo custo, usamos um multimap que já permite essas situações).

Finalmente a função cost. Começamos por assumir que estamos na casa (1,1) (os índices em C começam em 0, por isso é a casa (0,0)), e inserimos o custo dessa casa associado a ela no mapa. A seguir entramos num ciclo infinito, que só acaba quando entrarmos na casa final (infinito que acaba... ya). Em cada passo do ciclo, começamos por ver qual é a casa que está no início do mapa. Para isso usamos um iterator, e ele aponta para uma estrutura do tipo pair; o campo "first" é a chave e o campo "second" é o valor associado. O ponto fica na variável "cur" e o custo na "total". O ciclo "for" que se segue vai executar 4 vezes, tentado saltar para as 4 casas à volta da casa actual. O ponto "p" é esse novo ponto temporário. Depois temos 2 testes: o primeiro, vê se a casa nova é a final; se sim, a função retorna o custo total mais o custo da casa final. O outro teste verifica se o ponto é válido e se ainda não foi visitado, e nesse caso inserimos no mapa os novos dados: o custo total mais o custo desse novo ponto associado a esse ponto. A inserção no mapa garante que este novo elemento vai ficar na casa correcta, de modo que no próximo passo do algoritmo o primeiro elemento é o com menor custo. Esta operação é de complexidade O(log n). Finalmente, depois de fazer a expansão para as casas à volta, removemos a casa visitada do mapa e marcamo-la como visitada para que futuros passos do algoritmo não voltem lá.

Complicado? :) Não é, o código é que talvez não se compreenda à primeira. Convém perceber a ideia geral do algoritmo, e saber como se usa um multimap e iterators (STL...). É boa prática tentar resolver este problema do início, ou seja, re-implementar a solução.