Informatika gyűjtemény

Egy szinttel feljebb uj_wordgame.cpp

2004050607080910

<<  13. óra  >>

<<  Szójáték  >>

NézetNyomtat

uj_wordgame.cpp (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: 3 KB
/*
    Informatika: algoritmus szakkor
    Feladat: szojatek
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/13ora/szojatek
*/
#include <stdio.h>
#include <string.h>

#define MaxLen 21
#define MaxWords 1000

// Szavak
int WordNum;
char Word[MaxWords][MaxLen];
// A ket bemeneti szo indexe
int P, Q;
// Logikai valtozo: hogy a B szabaly van-e ervenyben
bool bBRule;
// Elszomszedsagi matrix
bool Edge[MaxWords][MaxWords];
// A szelessegi bejarashoz hasznalt tomb: az egyes szavak milyen messze vannak az elso szotol
int Dist[MaxWords];

bool ReadDict (const char *);
bool ReadTask (const char *);
bool WriteRes (const char *);

int FindWord (const char *);
void FindEdges (void);
void CheckNeighbourhood (const char *, const char *, bool &, bool &);
void BreadthFirstSearch (void);
void PrintMatrix (void);

int main (int AN, char * Args []) {
    if (AN < 4)
        return 1;
    if (!ReadDict(Args[1]))
        return 1;
    if (!ReadTask(Args[2]))
        return 1;
    FindEdges();
    BreadthFirstSearch();
    if (!WriteRes(Args[3]))
        return 1;
    return 0;
}

// Szotar beolvasasa
bool ReadDict (const char * FN) {
    FILE * F = fopen(FN, "r");
    if (F == NULL)
        return false;
    fscanf(F, "%d\n", &WordNum);
    for (int I = 0; I < WordNum; I++)
        fscanf(F, "%s\n", Word[I]);
    fclose(F);
    return true;
}
// Feladat beolvasasa
bool ReadTask (const char * FN) {
    FILE * F = fopen(FN, "r");
    char Rule, WordP[MaxLen], WordQ[MaxLen];
    if (F == NULL)
        return false;
    fscanf(F, "%c\n", &Rule);
    bBRule = Rule == 'B';
    fscanf(F, "%s\n", WordP);
    P = FindWord(WordP);
    fscanf(F, "%s\n", WordQ);
    Q = FindWord(WordQ);
    fclose(F);
    return P != -1 && Q != -1;
}
// Eredmeny kiirasa
bool WriteRes (const char * FN) {
    FILE * F = fopen(FN, "w");
    int I, Min = -1;
    if (F == NULL)
        return false;
    
    // Elso sor
    if (Dist[Q] != -1)
        fprintf(F, "IGEN %d\n", Dist[Q]);
    else
        fprintf(F, "NEM\n");
    
    // Masodik sor
    for (I = 0; I < WordNum; I++)
        if (Dist[I] != -1)
            fprintf(F, "%s ", Word[I]);
    fprintf(F, "\n");
    fclose(F);
    return true;
}

// Adott szora visszaadja az indexet a szotarban (vagy -1-et, ha nincs benne)
int FindWord (const char * A) {
    for (int I = 0; I < WordNum; I++)
        if (strcmp(Word[I], A) == 0)
            return I;
    return -1;
}
// Az elszomszedsagi matrix kitoltese
void FindEdges (void) {
    int I, J, K;
    for (I = 0; I < WordNum; I++)
        Edge[I][I] = 0;
    for (I = 0; I < WordNum; I++)
        for (J = I + 1; J < WordNum; J++)
            CheckNeighbourhood(Word[I], Word[J], Edge[I][J], Edge[J][I]);
}
// Ket elem szomszedsaganak vizsgalata
// AB: A-bol a B-be el lehet jutni
// BA: B-bol az A-ba el lehet jutni
void CheckNeighbourhood (const char * A, const char * B, bool & AB, bool & BA) {
    int I, X = 0;
    AB = BA = false;
    for (I = 0; A[I] && B[I]; I++)
        if (A[I] != B[I])
            X++;
    if (A[I] && B[I] == 0)
        BA = X == 0 && bBRule && A[I + 1] == 0;
    else if (B[I] && A[I] == 0)
        AB = X == 0 && bBRule && B[I + 1] == 0;
    else
        AB = BA = X == 1;
}
// Szelessegi bejaras
void BreadthFirstSearch (void) {
    int FIFO[MaxWords], FIn = 0, FOut = 0;
    int I;
    
    for (I = 0; I < WordNum; I++)
        Dist[I] = -1;
    Dist[P] = 0;
    FIFO[FIn++] = P;
    while (FIn > FOut) {
        for (I = 0; I < WordNum; I++)
            if (Edge[FIFO[FOut]][I] && Dist[I] == -1) {
                Dist[I] = Dist[FIFO[FOut]] + 1;
                FIFO[FIn++] = I;
            }
        FOut++;
    }
}
(Vissza)