Informatika gyűjtemény

Egy szinttel feljebb dom.c

2004050607080910

<<  1. óra  >>

<<  Dominófedés  >>

NézetNyomtat

dom.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: 5 KB
/*
 * Meszaros Balazs, 2006-09-20
 *
 * Forditas keprajzolas nelkul:
 * gcc -o dom dom.c -Wall
 * ./dom < bemenet > kimenet
 *
 * Forditas keprajzolassal (kell hozza libgd):
 * gcc -o dom dom.c -Wall -DKEP -lgd
 * ./dom < bemenet > kimenet 2> kep.png
 * Mivel a kep ebben az esetben az stderr-re irodik ki, tehat ezert van ott
 * a "2>".
 */
#include <stdio.h>

#ifdef KEP
#include <gd.h>

/* a negyzet merete hany pixel legyen */
#define NEGYZET 20
#endif

/* sorok szama */
size_t s;

/* oszlopok szama */
size_t o;

/* vonalak szama */
size_t vonalak;

/* az egesz tabla, amiben a dominok csucsulnek. a mezo erteke lehet:
 * D_URES: nincs ott domino
 * D_JOBB: van domino, ami jobbra nez
 * D_LE: van domino, ami lefele nez
 * D_MAS: van domino, aminek ez a masik vege */
char domino[100][100];

#define D_URES 0
#define D_JOBB 1
#define D_LE 2
#define D_MAS 3

/* a vonalak tombje, legfeljebb 120 vonal lehet. az a jeloli az elso mezot
 * b pedig a masodikat */
struct {
    unsigned short a;
    unsigned short b;
} vonal[120];

void nullaz(void)
{
    size_t i, j;

    for (i = 0; i < s; i++)
        for (j = 0; j < o; j++)
            domino[i][j] = D_URES;
}

int beolvas(void)
{
    size_t i, a, b;

    if (scanf("%u %u %u", &s, &o, &vonalak) != 3) {
        printf("hibas bemenet\n");
        return 0;
    }

    nullaz();

    for (i = 0; i < vonalak; i++) {
        if (scanf("%u %u", &a, &b) != 2) {
            printf("hibas bemenet\n");
            return 0;
        }

        vonal[i].a = a - 1;
        vonal[i].b = b - 1;
    }

    return 1;
}

/* atalakitja a sor, oszlop indexet a mezo indexeve */
#define MEZO(sor, oszlop) ((sor) * o + (oszlop))
/* kiszedi a mezo indexebol a sort */
#define MEZO_S(m) ((m) / (o))
/* kiszedi a mezo indexebol az oszlopot */
#define MEZO_O(m) ((m) % (o))

int nincs_vonal(size_t a, size_t b, size_t c, size_t d)
{
    unsigned short m, n;
    size_t i;

    if (a >= s || b >= o || c >= s || d >= o)
        return 0;

    m = MEZO(a, b);
    n = MEZO(c, d);

    for (i = 0; i < vonalak; i++)
        if ((vonal[i].a == m && vonal[i].b == n) ||
            (vonal[i].a == n && vonal[i].b == m))
            return 0;

    return 1;
}

#ifdef KEP
void kep(void)
{
    gdImagePtr im;
    int feher, fekete, piros;
    size_t i, j, maxx, maxy;
    unsigned short s1, o1, s2, o2, kx, ky;

    maxx = o * NEGYZET;
    maxy = s * NEGYZET;

    im = gdImageCreate(maxx + 1, maxy + 1);
    if (!im) {
        printf("nem tudom letrehozni a kepet\n");
        return;
    }

    /* szinek */
    feher = gdImageColorAllocate(im, 255, 255, 255);
    fekete = gdImageColorAllocate(im, 0, 0, 0);
    piros = gdImageColorAllocate(im, 255, 0, 0);

    /* keret */
    for (i = 0; i < s; i++)
        gdImageLine(im, 0, i * NEGYZET, maxx, i * NEGYZET, fekete);

    for (i = 0; i < o; i++)
        gdImageLine(im, i * NEGYZET, 0, i * NEGYZET, maxy, fekete);

    /* keret jobb es also szele */
    gdImageDashedLine(im, 0, maxy, maxx, maxy, fekete);
    gdImageDashedLine(im, maxx, 0, maxx, maxy, fekete);

    for (i = 0; i < vonalak; i++) {
        /* a mezo kozepe */
        s1 = MEZO_S(vonal[i].a) * NEGYZET + NEGYZET / 2;
        o1 = MEZO_O(vonal[i].a) * NEGYZET + NEGYZET / 2;

        /* a mezo kozepe */
        s2 = MEZO_S(vonal[i].b) * NEGYZET + NEGYZET / 2;
        o2 = MEZO_O(vonal[i].b) * NEGYZET + NEGYZET / 2;

        /* a vonal kellos kozepe */
        kx = (o1 + o2) / 2;
        ky = (s1 + s2) / 2;

        /* fuggoleges vonal */
        if (ky == s1)
            gdImageFilledRectangle(im, kx - 1, ky - NEGYZET / 2,
                           kx + 1, ky + NEGYZET / 2,
                           fekete);
        /* vizszintes */
        else
            gdImageFilledRectangle(im, kx - NEGYZET / 2, ky - 1,
                           kx + NEGYZET / 2, ky + 1,
                           fekete);
    }

    for (i = 0; i < s; i++)
        for (j = 0; j < o; j++)
            switch (domino[i][j]) {
            case D_JOBB:
                s1 = i * NEGYZET + NEGYZET / 4;
                o1 = j * NEGYZET + NEGYZET / 4;

                s2 = i * NEGYZET + NEGYZET * 3 / 4;
                o2 = (j + 1) * NEGYZET + NEGYZET * 3 / 4;

                gdImageFilledRectangle(im, o1, s1,
                               o2, s2, piros);

                break;
            case D_LE:
                s1 = i * NEGYZET + NEGYZET / 4;
                o1 = j * NEGYZET + NEGYZET / 4;

                s2 = (i + 1) * NEGYZET + NEGYZET * 3 / 4;
                o2 = j * NEGYZET + NEGYZET * 3 / 4;

                gdImageFilledRectangle(im, o1, s1,
                               o2, s2, piros);

                break;
            }

    gdImagePng(im, stderr);

    gdImageDestroy(im);
}
#endif

void kiir(void)
{
    size_t i, j;

    for (i = 0; i < s; i++)
        for (j = 0; j < o; j++)
            switch (domino[i][j]) {
            case D_JOBB:
                printf("%u %u\r\n",
                       MEZO(i, j) + 1, MEZO(i, j + 1) + 1);
                break;
            case D_LE:
                printf("%u %u\r\n",
                       MEZO(i, j) + 1, MEZO(i + 1, j) + 1);
                break;
            }

#ifdef KEP
    kep();
#endif
}

int stop = 0;

void rek(void)
{
    unsigned int m, i, j;

    if (stop)
        return;

    for (m = 0; m < s * o; m++) {
        i = MEZO_S(m);
        j = MEZO_O(m);

        if (domino[i][j] == D_URES)
            break;
    }

    if (m >= s * o) {
        kiir();
        stop = 1;
    }

    if (nincs_vonal(i, j, i, j + 1) && domino[i][j + 1] == D_URES) {
    //  printf("LETESZ %u (jobb)\n", MEZO(i, j) + 1);
        domino[i][j] = D_JOBB;
        domino[i][j + 1] = D_MAS;

        rek();

    //  printf("FELVESZ %u (jobb)\n", MEZO(i, j) + 1);
        domino[i][j] = D_URES;
        domino[i][j + 1] = D_URES;
    }

    if (nincs_vonal(i, j, i + 1, j) && domino[i + 1][j] == D_URES) {
    //  printf("LETESZ %u (le)\n", MEZO(i, j) + 1);
        domino[i][j] = D_LE;
        domino[i + 1][j] = D_MAS;

        rek();

    //  printf("FELVESZ %u (le)\n", MEZO(i, j) + 1);
        domino[i][j] = D_URES;
        domino[i + 1][j] = D_URES;
    }
}

int main(int argc, char **argv)
{
    if (!beolvas())
        return 1;

    rek();

    return 0;
}
(Vissza)