OMI 2011 Problema 1 ( Dementores a la puarte )

Problema:
Dementores a la puerta
¡Los temidos dementores están a las puertas de Hogwarts! Como de costumbre, será tarea de los amigos Harry Potter y Ron Weasley alejarlos de ahí. Para alejarlos ambos saben invocar el hechizo patronus. Cuando un mago invoca un patronus los dementores se alejan en dirección contraria al mago lo más posible. Por ejemplo, si el mago está del lado oeste, los dementores se alejarán hacia el este hasta chocar con algún obstáculo o pared. Si está del lado norte, los dementores se alejarán hacia el sur.
El patio de Hogwarts se representa como un cuadrado de lado N, Harry y Ron están en el lado oeste y norte del patio. El patio tiene O obstáculos internos. Inicialmente toda la fila norte (la fila superior) y la columna oeste (la columna hasta la izquierda) están
llenas de dementores.
La primer figura muestra el patio de Hogwarts, Harry está del lado oeste y Ron del lado norte. Los puntos negros son las casillas en donde hay dementores (en una casilla pueden haber múltiples dementores). Los cuadros grises son obstáculos y los dementores no pueden pasar a través de ellos, sin embargo, los patronus si atraviesan los obstáculos.
Aquí se muestra cómo quedan los dementores si Harry o Ron invocan su patronus. La izquierda muestra el resultado de Harry y derecha el resultado de Ron.
El objetivo de Harry y de Ron es llevar a todos los
dementores a la esquina inferior derecha del patio.
Como no son buenos para calcular, te pidieron que les digas cuál es el número mínimo de patronus que deben invocar entre los dos (cada uno de ellos puede invocar varios) para lograrlo.
Problema
Escribe un programa que dados los obstáculos del patio determine el número mínimo de patronus que se requieren para llevar a los dementores a la esquina inferior derecha.
Restricciones
1 < N <= 1,000 Dimensiones del patio
0 <= O <= 1,000,000 Número de obstáculos en el patio
Entrada
Tu programa debe leer del teclado los siguientes datos:
En la primera línea los números N y O, dimensiones del patio y número de obstáculos.
En las siguientes O líneas habrá 2 números enteros separados por un espacio en cada
una que indican la columna y la fila de cada uno de los obstáculos respectivamente. La esquina superior izquierda se representa como la posición (0, 0).
Salida
Tu programa debe escribir a la pantalla un único número entero que indique la cantidad mínima de patronus necesarios para llevar a todos los dementores a la esquina inferior derecha.
Te aseguramos que para todos los casos de prueba es posible lograr el objetivo.
OMI 2011 Problema 1 ( Dementores a la puarte )

Para encontrar la solución a este problema hay que ir de lo generar a lo particuluar, como podemos ver en el problema tenemos realmente n * 2 - 1 numero de dementores todos en la primera fila y primera columna ¿Por que digo que hay que ir de lo generar a lo particular?, bueno pues podemos pensar en resolver el problema moviendo todos los dementores al mismo tiempo o bien mejor moverlos uno por uno, primero pensemos cual es la
mejor manera de llevar a un dementor de su posición a la esquina inferior derecha, bueno si Harry lanza su patronus todos se mueven a la derecha, si Harry volviera a lanzar su patronus entonces no se movería ningún dementor, por lo tanto el siguiente movimiento siempre debe hacerlo Ron, y podemos ver pasa exactamente lo mismo si Ron lanza su patronus Harry debe ser el siguiente, entonces solo hay dos posibles solución que Ron lance su patronus primero o que Harry lo lance primero Ya con este primer paso podemos ver que solo hay que calcular el máximo tiempo que tarda cada dementor en llegar a su destino iniciando Harry primero y ver si es mejor que empezando con Ron

Ahora para cada dementor que este en la primera fila o primera columna, el mínimo para llegar a su destino, es saber si se moverá hacia abajo o hacia la derecha, si sabemos eso, entonces el siguiente paso será el movimiento diferente.
Para resolver esto utilizaremos programación dinámica en din[ direccion ][ posicionfila ][ posicioncol ], pero para hacer el movimiento mas rápido ya que si nos movemos hacia abajo tendríamos que movernos hasta llegar a un obstaculo o llegar al borde, primero pre calculamos la siguiente posición que nos corresponde si vamos hacia abajo, y para usamos el arreglo next[ direccion ][ posicionfila ][ posicioncol ] , que nos indica que si vamos hacia abajo en la posición fila , col next[ abajo = 0 ][ posicionfila ][ posicioncol ], nos indica la fila en la que acabaríamos y si pones next[ derecha = 1 ][ posicionfila ][ posicioncol ] nos indicaría la columna.
< br /> Veamos el código:

/* Autor : Rodrigo Burgos 
   Problema: Dementores a la puerta */
# include "string.h"
# include "stdio.h"

int mapa[1002][1002], n;
int next[2][1000][1001];
int din[2][1002][1002];

int min( int a, int b ){ return a < b ? a : b; }
int max( int a, int b ){ return a > b ? a : b; }

/* calculamos el minimo numero de movimientos para llegar a la esquina
   inferior derecha, desde la posicion a, b con direccion dir (0 : abajo, 1 : derecha) */
int solve(int dir, int a, int b ){
  int res;
  if( a == n - 1 && b == n - 1) return 0; /* Ya llege a mi destino */
  if( din[dir][a][b] != - 1) return din[dir][a][b];
  if( dir == 0 ){
   res = solve( (dir + 1) % 2 , next[dir][a][b], b ) + 1;
  }else{
   res = solve( (dir + 1) % 2 , a, next[dir][a][b]) + 1;
  }
  return din[dir][a][b] = res;
}

main(){
  int obs, a, b, x, y, dir;
  int sol, res;
  scanf("%d %d", &n, &obs);
  for( x = 0; x < obs; x++){
     scanf("%d %d", &a, &b); 
     mapa[ b ][ a ] = 1;
  }
  /* Todas las posiciones siguientes les asignamos como vacias*/
  memset( next, -1, sizeof( next )); 
  /* Calculamos las posiciones siguientes de cada una de las 
     cordenadas, si van hacia abajo hasta donde llegan , si van a la 
     derecha hasta donde llegan, dir = 0 ( abajo ) , dir = 1 ( derecha) */
  for( dir = 0; dir < 2; dir++){
     for( x = n - 1; x >= 0 ; x-- )
     for( y = n - 1; y >= 0 ; y-- ){
        if( dir == 0 ){ /* hacia abajo */
           if( mapa[x][y] == 0 ){ /* si no hay obstaculo */ 
          next[ dir ][ x ][ y ] = ( next[ dir ][ x + 1][ y ] == -1 ?  x  : next[ dir ][ x + 1 ][ y ]  );
           }
        }else{ /*  hacha la derecha */
           if( mapa[x][y] == 0 ){ /* si no hay obstaculo */ 
          next[ dir ][ x ][ y ] = ( next[ dir ][ x ][ y + 1 ] == -1 ?  y  : next[ dir ][ x ][ y  + 1 ] );
           }
        }
     }
  }
  sol = (1<<29);
  memset( din , -1, sizeof( din ));
  for( dir = 0; dir < 2; dir++){
   res = 0;
   for( x = 0; x < n; x++){
    res = max( res, solve(dir,  0, x ));
    res = max( res, solve(dir, x, 0 ));
   }
   sol = min( sol, res );
  }
  printf("%d\n", sol);
  return 0; 
}