Determine if a matrix can be divided into two such that it has the same number of special characters

Question

Determine if a matrix can be divided into two such that it has the same number of special characters

Navigation

#1 by (2 votes)

1

The following code seeks to determine if an array of size N, composed of "." and "#" can be split in two, such that the number of characters "#" in each piece is the same. The partition must be done horizontally or vertically, it can not be diagonal or zigzag. If this can be done, return "YES" otherwise "No". The input consists of a number T that will be the number of cases to be evaluated, the number N that is the size of the matrix and finally the matrix. For example:

This was the solution attempt

#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;
}

However, I notice that the code does not detect cases where it does not work. What part of the code could be failing, what do you recommend?

c++ algoritmos

asked by Jsanabria 08.10.2018 в 03:53

source

1 answer

How to send AJAX request with headers Send form to PHP

score 2 · Answer 1

This, once we catch the trick , is easier than it seems.

For vertical divisions, the logic is simple: go counting '#' from row to row , and go accumulating it.

If when we get to the last column of a row we have exactly half of symbols '#', it is possible to divide vertically.

This, at the same time, gives us the key to accelerate the process. We only have to count until we reach half of the total% of # . In your 2 test cases, we can stop counting when we reach 5 # .

The same is applicable to horizontal divisions; but, in this case, we are accumulating column to column . If at the end of a column we carry half, division is possible.

Well, to the point:

#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;
}

We could use RAII to save the 3 calls to delte[] , and even try to reuse matrix for the next case if the size is enough, but I think that obfuscates the central idea of the code, without contributing anything relevant. I leave it to the desire to investigate each one.