Translate

lunes, 16 de enero de 2012

USACO 2012 January Contest, Bronze Division, Problem 3. Grazing Patterns

USACO 2012 January Contest, Bronze Division, Problem 3. Grazing Patterns


Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=105
Despues de un rato de pensar como reducir el problema, ya que con programacion dinamica no se me ocurria como ( por que eran 2^25 estados en el peor de los casos ) , me di cuenta que no deberia haber muchas formas de que Bessie y Mildred pudieran comer todo el pasto, por tanto decidi hacer un bactracking.
Para este backtracking necesito leer el mapa que lo guardo en mapa , ya teniendo el mapa, en mi funcion para el backtraking llevo la posicion de Bessie y de Mildre su fila row y su columna col y el numero de pasto que aun no eh consumido, cada vez que entro a la funcion valido que no se allan salido del mapa , para esos son los if de la linea 17 y 18, despues valido que no que esas posiciones del mapa no allan sido visitadas antes por ninguna de las dos vacas, en la linea 19 se compara si la posicion de Bessie es la misma que la de Mildred y solo falta una celda de pasto count = 1 entonces regreso que encontre una forma, en otro caso si llegaron a la misma posicion pero les falto alguna zona por comer, en la line 50 y 51 se asigna la direcion a Bessie y a Mildred respectivamente, y en la linea 52 se manda a llamar de nuevo la funcion solve pero con las nuevas posiciones de Bessie y de Mildred, se incrementan dependiendo de su dirección , con los arreglos dx y dy estos arreglos nos ayudan a reducir el codigo ya que tienen asignadas 1, 0 o -1 para indicar que se incrementa la posicion en 1 o se decrementa por 1, en la lina 47 y 48 se marca el mapa como visitado y en la linea 53 y 54 se desmarca ( como todo backtracking).
Aqui el codigo:
/*
   Autor: Rodrigo Burgos Dominguez
   Problema: Grazing Patterns
*/
# include "stdio.h"
# include "string.h"

# define MAX 5

int mapa[ MAX + 1 ][ MAX + 1];
int dx[ 4 ] = { 0, 0, 1,-1};
int dy[ 4 ] = { 1,-1, 0, 0};

int solve( int BessieRow , int BessieCol, int MildredRow , int MildredCol , int count ){
  int BessieDir , MildredDir;
  int cont = 0;
  if( BessieRow < 0 || BessieRow >= MAX || BessieCol < 0 || BessieCol >= MAX ) return 0;
  if( MildredRow < 0 || MildredRow >= MAX || MildredCol < 0 || MildredCol >= MAX ) return 0;
  if( mapa[ BessieRow ][ BessieCol ] == 1 || mapa[ MildredRow ][ MildredCol ] == 1) return 0;
  if(  BessieRow == MildredRow && BessieCol == MildredCol ) return count == 1 ? 1 : 0;
  mapa[ BessieRow ][ BessieCol ] = 1;
  mapa[ MildredRow ][ MildredCol ] = 1;
  count -= 2;
  for( BessieDir = 0; BessieDir < 4; BessieDir++ )
  for( MildredDir = 0; MildredDir < 4; MildredDir++ )
     cont += solve( BessieRow + dx[ BessieDir ], BessieCol + dy[ BessieDir ], MildredRow + dx[ MildredDir ], MildredCol + dy[ MildredDir ] , count );
  mapa[ BessieRow ][ BessieCol ] = 0;
  mapa[ MildredRow ][ MildredCol ] = 0;
  return cont;
}

main(){
  int m, x, count = MAX * MAX , a, b;
  freopen("grazing.in", "r", stdin);
  freopen("grazing.out", "w", stdout);
  scanf("%d", &m);
  for( x = 0; x < m; x++ ){
    scanf("%d %d", &a, &b);
    if( mapa[a - 1][b - 1] == 0 ) count--;
    mapa[a - 1][b - 1] = 1;
  }
  printf("%d\n", solve( 0, 0, MAX - 1, MAX - 1, count ));
  return 0;
}



Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com


No hay comentarios: