Trabalhar com coordenadas..

[Guy]

Olá,

Seguinte estou ficando de cabelos brancos tentando resolver um exercício, não sei por onde começar... segue a descrição:

O escritório de uma fica no canto inferior esquerdo (0,0) e o posto do correio no ponto mais ao nordeste da cidade (A,L). O officeboy leva exatamente 1 minuto para se locomover por cada ponto do plano. Ele não pode se mover ao sul ou oeste do prédio da empresa nem ao norte ou leste do posto do correio (ou seja, sua coordenada x deve ser entre 0 e L e sua coordenada Y entre 0 e A). Adicionalmente, existem N interseções em construção e portanto o officeboy deve desviar durante seu trajeto. O número de rotas mais curtas podem ser muito grande portanto retorne este valor em modulo 1000000037. Se o caminho estiver bloqueado e for impossível chegar ao correio, a resposta deverá ser 0.

Regras

Entrada

As entradas devem iniciar com o inteiro T (<=40) em uma linha, representando o número de casos de teste. Cada caso de teste começa com 3 números inteiros separados por vírgula, representando A, L (<=107) e N (0, max(100,min(L,A,1000))), e então “:”. Em seguida deverá existir N conjuntos de inteiros X (<=L) e Y (<=A) separados por “;” que representam as coordenadas das interseções em obras que deverão ser evitadas. Estas interseções devem ser únicas entre 0,0 e A,L e não podem já estar em construção. Uma linha em branco deve separar cada caso de teste.

Saída

Cada caso de teste deve retornar uma linha contendo o número de rotas mais curtas, modulo 1000000037.

Exemplo

Entrada:

3

2,2,1:1,1;

1,1,2:0,1;1,0;

7,1,2:1,0;4,1;

Saída:

2

0

6

Editado Janeiro 10, 2013 por Guy