Joven Club


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 1G

Authors:
Problem types
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

Al Palacio Central de los Joven Club de cierta provincia del país llega la encomienda por parte de la Dirección de Educación de crear un pequeño carro inteligente para el uso y disfrute de los niños en círculos de interés de robótica.

El carrito va a funcionar sobre una mesa y no se puede caer por el borde. Se debe tener en cuenta que el mismo no cuenta con sensor de proximidad, por lo tanto, solo se conocen las posiciones donde él puede detenerse gracias a un obstáculo. La mesa puede ser representada por una cuadrícula con H filas horizontales y W columnas verticales. Sean (i,j) el cuadrado en la i-ésima fila desde arriba y j-ésima columna desde la izquierda. A la mesa se le pueden colocar N obstáculos. El i-ésimo obstáculo se coloca en (X_{i},Y_{i}). En cada movimiento el carrito debe decidir una de las cuatro direcciones, arriba, abajo, izquierda o derecha, y sigue moviéndose hasta que choca con un obstáculo. Cuando golpea un obstáculo, se detiene en el cuadrado justo antes del obstáculo. Queda prohibido iniciar un movimiento en el que nunca chocará con un obstáculo para evitar su caída. El carrito está inicialmente en (s_{x},s_{y}). Se desea que haga una serie de movimientos para detenerse en (g_{x},g_{y}). Encuentre el número mínimo de movimientos requeridos para terminar en (g_{x},g_{y}). Si no es posible, denunciar el hecho.

Restricciones

  • 1\leq H \leq 10^9
  • 1\leq W \leq 10^9
  • 1\leq N \leq 10^5
  • 1\leq s_x,g_x\leq H
  • 1\leq s_y,g_y\leq W
  • 1\leq X_i \leq H
  • 1\leq Y_i \leq W
  • (s_x,s_y)\neq (g_x,g_y)
  • (s_x,s_y)\neq (X_i,Y_i)
  • (g_x,g_y)\neq (X_i,Y_i)
  • Si i\neq j, entonces (X_i,Y_i)\neq (X_j,Y_j).

Todos los valores en la entrada son enteros.

Entrada

La entrada se proporciona desde la entrada estándar con el siguiente formato:

H W N

s_x s_y

g_x g_y

X_1 Y_1

X_2 Y_2

\vdots

X_N Y_N

Salida

Imprime el número mínimo de movimientos requeridos para terminar en (g_x,g_y). Si es imposible terminar allí, imprima -1.

Ejemplo #1 de Entrada

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

Ejemplo #1 de Salida

4

En la figura, (s_x,s_y) están representado por S y (g_x,g_y) por G. Al moverse como (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), puede terminar en (g_x,g_y) con 4 movimientos.

Ejemplo #2 de Entrada

4 6 2
3 2
3 5
4 5
2 5

Ejemplo #2 de Salida

-1

El tiene que parar en (g_x,g_y). Tenga en cuenta que simplemente pasar por (g_x,g_y) no se considera que termina en la meta.

Ejemplo #3 de Entrada

1 10 1
1 5
1 1
1 7

Ejemplo #3 de Salida

-1

Si elige moverse hacia la izquierda, el carrito caerá por el borde de la mesa después de atravesar (g_x,g_y). Tenga en cuenta que está prohibido iniciar un movimiento en el que nunca chocará con un obstáculo, ya que el carrito caería por el borde de la mesa.


Comments

There are no comments at the moment.