Translate

jueves, 31 de octubre de 2013

2457 - Piece Creation (Programación Dinamica COJ)

2457 - Piece Creation

Este problema nos dice que teniendo puntos en un tablero, nosotros podemos trazar líneas horizontales y verticales que conecten el punto con el extremo del tablero, con la restricción de que no toque otro punto o otra línea que conecte otro punto con la orilla del tablero ( Esto es un circuito electrónico que conecta un punto del circuito con la orilla ya que en la orilla esta la corriente). La tarea es encontrar el costo mínimo de hacer esto, ya que cada cm de línea que utilicemos tiene un costo.

Lo primero que se me ocurrió fue hacer un flujo máximo a costo mínimo, cada punto del tablero serian dos nodos un nodo incidente y otro adyacente, donde cada nodo incidente y adyacente que represente un nodo tendría una arista de costo 1 o de capacidad 1 , esto para evitar que pasara por el mas de un cable , si existiera un punto en esta coordenada simplemente esta arista no existiría, y de hecho resolvía el problema general, de conectar con el mínimo cable todos los puntos, pero el problema tiene una restricción, que solo pueden ser líneas rectas, esta solución encuentra un cableado donde se puede modificar la dirección del cable.

Después de pensar un rato mas encontré algo interesante, que es el tamaño del chip ( o del tablero) es menor a 30, y solo hay 50 puntos , si nosotros ordenamos de menor a mayor , por coordenadas Y y posteriormente por X, tenemos que cuando coloquemos un punto P[pos] después de P[pos - 1 ], este punto o esta arriba ( P[pos-1].y < P[pos - 1].Y ) o esta a la derecha ( P[pos-1].x < P[pos].x) , con esto podemos saber dos cosas, primero si puedo conectar el punto P[pos] a la derecha , ya que si P[pos-1].y == P[pos].y no es posible, y llevando el control del rango [A,B], donde A es el punto donde inicia el tablero visible de arriba y B es la posición del tablero donde termina el espacio visible, a que me refiero con campo visible, por ejemplo el campo visible al inicio es de 0 a 31, si un punto esta en la coordenada X = 5 y se conecta con otro a la izquierda tapa todos los nodos del 0 al 5 entonces el campo visible de tablero superior es de 6 al 31, si existiera otro que fuera a la derecha a partir de X = 9 , se tendría un campo visible de 6 al 8, entonces si nosotros llevamos esto en nuestra dinámica o mejor dicho en nuestra memorización , podríamos saber si puedo conectarme arriba y a la izquierda y como siempre se puede conectar a la derecha , casi se tiene resuelto el problema, para resolver el problema de si puede ir hacia abajo , simplemente llevamos otro rango [a,b], este rango es el rango permitido de colocar un punto, si nosotros colocamos un punto que va hacia abajo partiría en dos el tablero, y si un punto se quiere conectar al a izquierda solo podría hacerlo si el b = 31 , o si quiere ir a la derecha tendría que a ser igual a cero ( a=0) , si garantizamos que al partir el tablero ( conectarlo hacia abajo no hay un punto en ese trayecto) entonces solo restaría agregar los puntos siguiente dependiendo si están de lado de una partición o si están del otro lado. Aquí les dejo el código:

/*Autor: Rodrigo Burgos Dominguez*/

# include "stdio.h"
#include "string.h"

typedef struct { int x,  y;  } POINT;

POINT p[100];
int AA, n;

int compare( POINT *a, POINT *b){
  if( a->y != b->y)
   return a->y - b->y; 
  return a->x - b->x;
}

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

int din[51][32][32][32][32];
int mapMax[100];
int mapMin[100];

int ladosMax[100];
int ladosMin[100];

int solve( int position, int A, int B, int a, int b){
  int res = (1<<22), path = -1, tres, cst = 0;
  if( position >= n ) return 0;
  if( din[position][A][B][a][b] != -1) return din[position][A][B][a][b];
  if( p[position].x <= a || p[position].x >= b ) 
    return din[position][A][B][a][b] = solve( position + 1, A, B, a, b);
   /* ARRIBA */
  if( p[position].y <= mapMin[ p[ position ].x ] && p[ position ].x < B && p[ position ].x > A){
    tres = solve( position + 1 , A, B, a, b ) + p[ position ].y ;
    if( tres < res ){
       res = tres;
       path = 0;
       cst = p[ position ].y;
    }
  }
  /* IZQUIERDA */
  if( p[position].x <= ladosMin[ p[ position ].y ] && a == 0 ){
    tres = solve( position + 1 , max( A, p[ position].x), B, a, b ) + p[ position ].x ;
    if( tres < res){
       res = tres;
       path = 1;
       cst = p[ position ].x; 
    }
  }
  /* DERECHO */
  if( p[position].x >= ladosMax[ p[ position ].y ] && b == 31 ){
    tres =  solve( position + 1 , A, min( B, p[position].x ), a, b ) + ( AA - p[ position ].x);
    if(tres < res){
      res = tres;
      path = 2;
      cst =  ( AA - p[ position ].x);
    }
  }
  /* ABAJO */
  if( p[position].y >= mapMax[ p[ position ].x ]){
    tres = solve( position + 1 , A, B, a, p[ position].x  )  + solve( position + 1, A, B, p[ position ].x , b)+ ( AA - p[ position ].y );
    if( tres < res){
       res = tres;
       path = 3; 
       cst = ( AA - p[ position ].y );
    }
  }
/*  printf("(%d %d) %d %d %d %d %d -> %d -> path %d cost %d\n", p[position].x, p[ position].y, position, A, B, a, b, res, path, cst);*/
  return din[position][A][B][a][b] = res; 
}

main(){
  int x, res;
  while( scanf("%d %d", &AA, &n) != EOF ){
     memset( din, -1, sizeof( din ));
     for( x = 0; x <= AA; x++){
      mapMax[ x ] = -(1<<22);
      mapMin[ x ] = (1<<22);
      ladosMax[x] = -(1<<22);
      ladosMin[x] = (1<<22);
     }
     for( x = 0; x < n; x++){
      scanf("%d %d", &p[x].x, &p[x].y); 
      mapMax[ p[x].x ] = max(mapMax[ p[x].x ], p[x].y);
      mapMin[ p[x].x ] = min(mapMin[ p[x].x ], p[x].y);
      ladosMax[ p[x].y ] = max(ladosMax[ p[x].y ] ,  p[x].x);
      ladosMin[ p[x].y ] = min(ladosMin[ p[x].y ] ,  p[x].x);
     }
     qsort( p, n, sizeof( POINT ), compare );
     res = solve( 0, 0, 31, 0, 31);
     if(res >= (1<<22))
       printf("No solution\n");
     else
       printf("The total length of wire used is %d\n", res);
  }
  return 0; 
}

No hay comentarios: