Jump to content
Fórum Script Brasil
  • 0

Trabalhar com coordenadas..


Guy

Question

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

Edited by Guy
Link to comment
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



  • Forum Statistics

    • Total Topics
      152.1k
    • Total Posts
      651.8k
×
×
  • Create New...