1

El siguiente código busca determinar si una matriz de tamaño N, compuesta de caracteres "." y "#" puede partirse en dos, tal que el numero de caracteres "#" en cada pieza sea el mismo. La partición debe hacerse de forma horizontal o vertical, no se puede diagonal ni en zigzag. Si esto se puede hacer, devuelve "YES" de lo contrario "No". La entrada se compone de un numero T que sera el numero de casos a evaluar, el numero N que es el tamaño de la matriz y finalmente la matriz. Por ejemplo: introducir la descripción de la imagen aquí

Este fue el intento de solucion

#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int T, N, ca = 0, fa = 0, cd, fd, l, j, k, i;
    bool oso = 0;

    cin >> T;
    for (i = 0; i < T; ++i) {
        cin >> N;
        char cho[N][N];
        for (int i = 0; i < N; i++)
            scanf("%s", cho[i]);
        int col[N] = { 0 };
        int fil[N] = { 0 };
        for (k = 0; k < N; ++k) {
            for (j = 0; j < N; ++j) {
                if ((cho[k][j] == '#') && (cho[j][k] == '#')) {
                    col[j] += 1;
                    fil[j] += 1;
                } else if (cho[j][k] == '#') {
                    fil[j] += 1;
                } else if (cho[k][j] == '#') {
                    col[j] += 1;
                }
            }
        }
        for (j = 1; j < N; ++j) {
            cd = 0;
            fd = 0;
            ca += col[j - 1];
            fa += fil[j - 1];
            for (l = N - 1; l >= j; --l) {
                cd += col[l];
                fd += fil[l];
            }
            if ((ca == cd) || (fa == fd)) {
                oso = 1;
                break;
            }
        }
        if (oso == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

No obstante, noto que el codigo no detecta los casos en que no sirve. ¿Qué parte del codigo podría estar fallando?¿qué me recomiendan?

1
  • ¿Cómo se tienen en cuenta las tablas con columnas impares? el 8 oct. 2018 a las 6:52

1 respuesta 1

2

Esto, una vez que le cogemos el truco, es mas fácil de lo que parece.

Para divisiones verticales, la lógica es simple: ir contando '#' de fila en fila, e ir acumulandolo.

Si al llegar a la última columna de una fila llevamos exactamente la mitad de símbolos ´#´, es posible dividir de forma vertical.

Esto, al mismo tiempo, nos da la clave para acelerar el proceso. Solo tenemos que contar hasta que lleguemos a la mitad del total de #. En tus 2 casos de prueba, podemos parar de contar al llegar a 5 #.

Los mismo es aplicable a divisiones horizontal; pero, en este caso, vamos acumulando columna a columna. Si al terminar una columna llevamos la mitad, la división es posible.

Bueno, al grano:

#include <iostream>

bool testVertical( const char *buff, int size, int count ) {
  int subtotal = 0;
  int lamitad = count / 2;

  for( int idx = 0; idx < ( size * size ); ++idx ) {
      if( idx && ( !( idx % size ) ) ) {
        if( subtotal == lamitad ) return true;
        if( subtotal > lamitad ) return false;
      }

      if( buff[idx] == '#' ) ++subtotal;
  }
  return false;
}

bool testHorizontal( const char *buff, int size, int count ) {
  int subtotal = 0;
  int lamitad = count / 2;

  for( int col = 0; col < size; ++col ) {
    if( subtotal == lamitad ) return true;
    if( subtotal > lamitad ) return false;

    for( int fila = 0; fila < size; ++fila ) if( buff[col + (fila * size)] == '#' ) ++subtotal;
  }

  return false;
}

int main( ) {
  int cases;

  std::cin >> cases;

  for( int n = 0; n < cases; ++n ) {
    int size;

    std::cin >> size;

    int count = 0;
    char *matrix = new char[size * size];
    char *idx = matrix;

    for( int curr = 0; curr < ( size * size ); ++curr ) {
      char simb[2] = { 0 };

      std::cin >> simb;
      *idx = simb[0];
      ++idx;
      if( simb[0] == '#' ) ++count ;
    }
    *idx = 0;

    // Casos especiales.
    // Todo #, ninguna #
    if( ( !count ) || ( count == ( size * size ) ) ) {
      std::cout << "YES";
      delete[] matrix;
      continue;
    }

    // El número de # es impar.
    if( count & 1 ) {
      std::cout << "NO";
      delete[] matrix;
      continue;
    }

    // Tenemos que calcularlo.
    if( testVertical( matrix, size, count ) ) std::cout << "Vertical: YES\n";
    if( testHorizontal( matrix, size, count ) ) std::cout << "Horizontal: YES\n";

    delete[] matrix;
  }

  return 0;
}

Podríamos usar RAII para ahorrarnos las 3 llamadas a delte[], e incluso intentar reutilizar matrix para el siguiente caso si el tamaño es suficiente, pero creo que ofusca la idea central del código, sin aportar nada relevante. Lo dejo a las ganas de investigar de cada uno.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.