Google Code Jam 2010: Making Chess Boards

Making Chess Boards (fazendo tabuleiros de xadrez) foi o terceiro e último problema da rodada !C do Google Code Jam 2010. Segundo a análise oficial, seria uma combinação de parsing, programação dinâmica e truques espertos. Embora eu tenha resolvido com sucesso o problema, minha solução envolve somente parsing e força bruta.

O Problema

O enunciado é simples. Temos um placa retangular que contem MxN quadrados (alguns pretos e outros brancos) e queremos fazer tabuleiros de xadrez. Em cada etapa retiramos o maior tabuleiro de xadrez possível, se tiver mais de um damos preferência ao que fica mais acima na placa, se ainda assim tivermos um empate pegamos o que fica mais à esquerda. Este processo deve ser repetido até usarmos toda a placa (se necessário fazemos tabuleiros 1x1). O programa de listar os tamanhos dos tabuleiros obtidos e a quantidade de cada tamanho.

Um tabuleiro de xadrez deve, é claro, alternar quadrados pretos e brancos na horizontal e vertical.

A dimensão horizontal (N) é sempre múltipla de quatro. Na entrada cada linha da placa é descrita como um número hexadecimal, cada bit corresponde a um quadrado (0 corresponde a preto e 1 a branco).

Minha Solução

Representei a placa como uma matriz de caracteres. Uma posição contém '0' se é preta, '1' se é branca ou 'X' se já foi usada.

A parte de análise da entrada (parsing) é bastante trivial. Cada dígito hexa é convertido em um número, os bits são testados e a matriz preenchida de acordo.

Em seguida procuro os tabuleiros. A rotina Count(t) procura, marca e conta os tabuleiros de tamanho t. A busca é feita percorrendo a matriz de cima para baixo e da esquerda para direita, de forma a encontrar os tabuleiros na ordem especificada. Temos portanto um laço por coluna ("for (j ...") dentro de um laço por linha ("for (i ...") para gerar os cantos superiores esquerdos. Para cada par (i,j) temos mais dois laços aninhados para verificar se temos a alternância de cor necessária nos dois sentidos. Se tudo der certo, marcamos como usados os quadrados do tabuleiro. Por último, se Count encontrou pelo menos um tabuleiro, anota o tamanho e quantidade em result.

O programa principal chama Count variando o tamanho do máximo possível até1. Deposi é só listar result.

É uma solução bastante direta e pouco otimizada, mas foi suficiente para resolver o large input em menos de três minutos no meu velho Pentium 4 2.8HT.

O Código

//
// Google CodeJam 2010 - Round 1C, Problem C
// DQuadros
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FALSE   0
#define TRUE    1

char bark [512][512];
int N, M;

struct
{
    int tam;
    int n;
} result [512];
int nr;

void Count (int t)
{
    int i, i1;
    int j, j1;
    char cr, cc;
    int found = FALSE;
    int ok;

    result[nr].tam = t;
    result[nr].n = 0;
    for (i = 0; i <= (M-t); i++)
    {
        for (j = 0; j <= (N-t); j++)
        {
            cr = bark[i][j];
            if (cr == 'X')
                continue;
            ok = TRUE;
            for (i1 = 0; ok && (i1 < t); i1++)
            {
                cc = cr;
                for (j1 = 0; ok && (j1 < t); j1++)
                {
                    if (bark[i+i1][j+j1] != cc)
                        ok = FALSE;
                    cc = cc ^ 1;
                }
                cr = cr ^1;
            }
            if (ok)
            {
                found = TRUE;
                result[nr].n++;
                for (i1 = 0; i1 < t; i1++)
                    for (j1 = 0; j1 < t; j1++)
                        bark[i+i1][j+j1] = 'X';
            }
        }
    }
    if (found)
        nr++;
}

void main (void)
{
    int iCase, nCases;
    int i, j;
    int h;
    int t;
    char hex [130];

    scanf ("%d\n", &nCases);
    for (iCase = 1; iCase <= nCases; iCase++)
    {
        scanf ("%d %d\n", &M, &N);
        for (i = 0; i < M; i++)
        {
            scanf ("%s\n", hex);
            for (j = 0; j < N/4; j++)
            {
                if (hex[j] <= '9')
                    h = hex[j] - '0';
                else
                    h = hex[j] - 'A' + 10;
                if (h & 8)
                    bark [i][j*4] = '1';
                else
                    bark [i][j*4] = '0';
                if (h & 4)
                    bark [i][j*4+1] = '1';
                else
                    bark [i][j*4+1] = '0';
                if (h & 2)
                    bark [i][j*4+2] = '1';
                else
                    bark [i][j*4+2] = '0';
                if (h & 1)
                    bark [i][j*4+3] = '1';
                else
                    bark [i][j*4+3] = '0';
            }
        }
        nr = 0;
        t = M;
        if (N < M)
            t = N;
        while (t > 0)
        {
            Count (t);
            t--;
        }
        printf ("Case #%d: %d\n", iCase, nr);
        for (i = 0; i < nr; i++)
            printf ("%d %d\n", result[i].tam, result[i].n);
    }
}