Informatika gyűjtemény

Egy szinttel feljebb haromszog.c

2004050607080910

<<  21. óra  >>

<<  Háromszög  >>

NézetNyomtat

haromszog.c (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 2 KB
#include <stdio.h>
#include <stdint.h>
#include <ctype.h>

uint8_t tabla[100][199];
int8_t h[100][199];
size_t n;

int beolvas(void)
{
    unsigned char ch;
    size_t i, j, start, stop;

    if (scanf("%u", &n) != 1)
        return 0;

    if (n == 0)
        return 0;

    for (i = 0; i < n; i++)
        for (j = 0; j < 2 * n - 1; j++)
            tabla[i][j] = ' ';

    start = 0;
    stop = 2 * n - 1;

    for (i = 0; i < n; i++) {
        for (j = start; j < stop; j++) {
            while (scanf("%c", &ch) == 1 && isspace(ch));

            tabla[i][j] = ch;
        }

        start++;
        stop--;
    }

    return 1;
}

void nullaz(void)
{
    size_t i, j;

    for (i = 0; i < n; i++)
        for (j = 0; j < 2 * n - 1; j++)
            h[i][j] = -1;
}

size_t maximum1(int sor, int oszlop)
{
    size_t a, b, c, r;

    if (sor < 0)
        return 0;

    if (h[sor][oszlop] >= 0)
        return h[sor][oszlop];

    a = maximum1(sor - 1, oszlop - 1);
    /* a maximum1(sor - 1, oszlop) fuggvenyt nem hivjuk meg, mert ott nem
     * kezdodhet haromszog, mert rossz az allasa, csak azt kell vizsgalni,
     * hogy oda rakhatunk-e */
    if (sor == 0 || tabla[sor - 1][oszlop] == '#') {
        b = 0;
    } else {
        b = a;
    }
    c = maximum1(sor - 1, oszlop + 1);

    /* ezt csak a rekurzio utan hivjuk meg, mert le kell mennie */
    if (tabla[sor][oszlop] == '#') {
        r = 0;
    } else {
        size_t min;

        min = (a < b) ? a : b;
        min = (min < c) ? min : c;

        r = min + 1;
    }

    h[sor][oszlop] = r;

    return r;
}

size_t maximum2(int sor, int oszlop)
{
    size_t a, b, c, r;

    if (sor >= n || oszlop < sor || 2 * n - 2 - oszlop < sor)
        return 0;

    if (h[sor][oszlop] >= 0)
        return h[sor][oszlop];

    a = maximum2(sor + 1, oszlop - 1);
    /* a maximum2(sor + 1, oszlop) fuggvenyt nem hivjuk meg, mert ott nem
     * kezdodhet haromszog, mert rossz az allasa, csak azt kell vizsgalni,
     * hogy oda rakhatunk-e */
    if (sor >= n || tabla[sor + 1][oszlop] == '#') {
        b = 0;
    } else {
        b = a;
    }
    c = maximum2(sor + 1, oszlop + 1);

    /* ezt csak a rekurzio utan hivjuk meg, mert le kell mennie */
    if (tabla[sor][oszlop] == '#') {
        r = 0;
    } else {
        size_t min;

        min = (a < b) ? a : b;
        min = (min < c) ? min : c;

        r = min + 1;
    }

    h[sor][oszlop] = r;

    return r;
}

void megold()
{
    size_t i, j, k;
    int m = 0;

    nullaz();
    maximum1(n - 1, n - 1);
    for (i = 0; i < n; i++)
        for (j = 0; j < 2 * n - 1; j++)
            if (m < h[i][j])
                m = h[i][j];

    nullaz();
    for (k = 1; k < 2 * n - 1; k += 2)
        maximum2(0, k);

    for (i = 0; i < n; i++)
        for (j = 0; j < 2 * n - 1; j++)
            if (m < h[i][j])
                m = h[i][j];

    printf("%u\n", m * m);
}

void kiir(void)
{
    int i, j;

#if 0
    printf("--- %u ---\n", n);

    for (i = 0; i < n; i++) {
        for (j = 0; j < 2 * n - 1; j++) {
            printf("%c", tabla[i][j]);
        }
        printf("\n");
    }

    printf("---- megoldas ----\n");
#endif
    megold();

#if 0
    for (i = 0; i < n; i++) {
        for (j = 0; j < 2 * n - 1; j++) {
            printf("%u", h[i][j]);
        }
        printf("\n");
    }
#endif
}

int main(void)
{
    while (beolvas())
        kiir();

    return 0;
}
(Vissza)