Descrição
Rafael, em seu primeiro dia de trabalho no zoológico da cidade, foi incubido da tarefa aplicada a todos os novatos: cuidar das tartarugas. Rafael achou aquilo tão fácil que resolveu tirar um cochilo em seu turno, porém quando acordou se viu em uma situação complicada, uma vez que as tartarugas estavam fugindo.
Como está em seu primeiro dia de trabalho, Rafael não quer decepcionar o chefe do zoológico, portanto está decidido a parar todas as tartarugas na menor quantidade de tempo possível.
O terreno em que eles estão pode ser visto como um plano, e Rafael está na posição [x, y]. A cada segundo, Rafael consegue se mover no máximo duas posições no sentido horizontal ou vertical, ou no máximo uma posição no sentido diagonal.
Rafael tem que parar três tartarugas, as quais estão nas posições [x1, y1], [x2, y2] e [x3, y3], respectivamente. As tartarugas, por sua vez, podem se mover apenas uma posição por segundo, e em apenas uma direção predeterminada: Cima ([xi, yi+1]) ou Direita ([xi+1, yi]). Elas estão sempre se movendo.
Para parar uma tartaruga Rafael precisa estar na mesma posição que tal tartaruga. Rafael pode escolher parar as tartarugas na ordem que ele desejar. Descubra a menor quantidade de tempo necessário para que ele pare as três tartarugas.
Entrada
Haverá diversos casos de teste. Cada caso de teste é iniciado com dois inteiros x e y (1 ≤ x, y ≤ 1000), indicando que Rafael está na posição [x, y] do plano.
A seguir haverá três linhas, cada uma contendo dois inteiros xi e yi (1 ≤ xi, yi ≤ 1000), indicando que a i-ésima tartaruga está na posição [xi, yi], e um caractere ci, indicando a direção que a i-ésima tartaruga está correndo: D – Direita, ou C – Cima.
O plano em que Rafael e as tarturugas estão se estende da posição [1, 1] (canto inferior esquerdo) até a posição [105, 105] (canto superior direito), portanto há bastante espaço para a perseguição. Duas tartarugas nunca estarão no mesmo lugar ao mesmo tempo.
O último caso de teste é indicado por x = y = 0, o qual não deverá ser processado.
Saída
Para cada caso de teste imprima um inteiro, representando a quantidade mínima de tempo necessária para capturar todas as tartarugas, na ordem desejada por Rafael.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
1 1 |
5 |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Cristhian Bonilha | Adaptado por erich.rodriguesf |