Problema A : Attacking rooks (Regional Latinoamerica)

Escrito por Rodrigo Burgos Domínguez

Problema A : Attacking rooks ( Regional Latino America 2013) Un problema un poco complejo de regional 2013 de Mexico, practicamente trata de dado una cuadricula de N x N , y unas celdas bloqueadas, es colocar el maximo numero de torres ( torre de ajedrez se mueve en toda su columna y toda su fila si no encuentra obstáculo), de tal manera que ninguna torre se ataque entre si.

Lo primero que uno debe observar que una torre puede bloquear una columna completa y una fila completa, entonces por cada posición del tablero si uno coloca una torre en esa posición bloquea la columna y fila de dicha posición, estas filas y columnas que nos referimos no es la fila completa del tablero si no una subparte de dicha fila ya que puede estar delimitada por puntos bloquedos ( o peones en el problema).

Para formar todos las sub filas y utilizo estos fors:

   newFil = 0;
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
         fils[r][c] = fils[r][c - 1];
        }
       }
      }
      

como se puede analizar lo que hace es marcar como una nueva fila, las subpartes cada que encuentra una posición bloqueada incrementa en esa posición un nueva fila y para todas las demás le asigna el numero de la fila de la posición bloqueada. ( en el caso de ser inicio de fila tambien se asigna una nueva fila).

Ya con eso podemos hacer una relación de subFiles y subColumnas, y lo que hay que maximizar es el numero de conexiones que hay entre las filas y columnas, en pocas palabras utilizar maximo matching.

Les comporta la solucion general del problema:

/* Rodrigo Burgos */

# include 
# include 

# define MAX 100
char map[MAX + 3][MAX + 3];
int cols[MAX + 3][MAX + 3];
int fils[MAX + 3][MAX + 3];
int mark[MAX * MAX + 2], vis[ MAX * MAX + 2];
char graph[MAX*MAX/2+1][MAX*MAX/2+1];

int newFil, newCol;

int match(int nodo ){
  int x;
  if( vis[nodo] == 1 ) return 0;
  vis[nodo] = 1;
  for( x = 1; x <= newCol; x++)
    if( graph[nodo][x] == 1 && ( mark[ x ] == -1 || match( mark[ x ])) ){
       mark[x] = nodo;
       return 1; 
    }
  return 0;
}

main(){
  int r, c, cont, x, n; 
   while( scanf("%d", &n) != EOF ) {
      memset( cols, 0, sizeof( cols ) );
      memset( fils, 0, sizeof( fils ) );
      for( x = 1; x <= n; x++) scanf("%s", map[x] + 1);
      newFil = newCol = 0;
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( cols[r - 1][c] == 0 ) cols[r - 1][c] = ++newCol;
         cols[r][c] = cols[r - 1][c];
        }
       }
      }
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++){
        if( map[r][c] != 'X'){
         if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
         fils[r][c] = fils[r][c - 1];
        }
       }
      }
      memset( graph, 0, sizeof( graph ) );
      for( r = 1; r <= n; r++){
       for( c = 1; c <= n; c++)
         if( map[r][c] != 'X'){
          graph[fils[r][c]][cols[r][c]] = 1;
         }
      }
      memset( mark, -1, sizeof( mark ) );
      cont = 0;
      for( x = 1; x <= newFil; x++){
        memset( vis, 0, sizeof( vis ) );
        if( match( x ) ) cont++;
      }
      printf("%d\n", cont);
   }
   return 0; 
}