Ir para conteúdo
Fórum Script Brasil
  • 0

Trabalhar com coordenadas..


Guy

Pergunta

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 por Guy
Link para o comentário
Compartilhar em outros sites

0 respostass a esta questão

Posts Recomendados

Até agora não há respostas para essa pergunta

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152,3k
    • Posts
      652,4k
×
×
  • Criar Novo...