Informatika gyűjtemény

Egy szinttel feljebb idegen.cpp

2004050607080910

<<  10. óra - Szélességi és mélységi bejárás  >>

<<  Idegenvezetés  >>

NézetNyomtat

idegen.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: utf-8
Méret: 2 KB
#include <stdio.h>
#include "matrix.h"

#define MaxLen 20
#define MaxN 100

/*
    Mélységi bejárás és alkalmazása.
    A programot Uray M. János készítette 2008. november 25-én.
*/

int bConnected (const cMatrix &);
void Recursion (const cMatrix &, int, int *);

int main (int AN, char * Args []) {
    FILE * IF, * OF;
    cMatrix M, M_;
    char Names[MaxN][MaxLen + 1], Line[MaxLen + 1], * P;
    int I, J, K, L, N, R, X[2], B[MaxN], NB, NN = 0;

    printf("<-- Start -->\n");
    if (AN < 3)
        return 1;
    // Fájlok megnyitása
    IF = fopen(Args[1], "rt");
    if (IF == NULL)
        return 1;
    OF = fopen(Args[2], "wt");
    if (OF == NULL) {
        fclose(IF);
        return 1;
    }
    while (1) {
        // Csúcsok beolvasása
        fscanf(IF, "%d\n", &N);
        if (!N)
            break;
        M.Set(N, N);
        for (I = 0; I < N; I++)
            fscanf(IF, "%s\n", Names[I]);
        fscanf(IF, "%d\n", &R);
        M.Empty();
        // Élek beolvasása
        for (I = 0; I < R; I++) {
            for (J = 0; J < 2; J++) {
                fscanf(IF, "%s\n", Line);
                for (K = 0; K < N; K++) {
                    for (L = 0; Line[L]; L++)
                        if (Names[K][L] != Line[L])
                            break;
                    if (!Line[L])
                        break;
                }
                X[J] = K;
            }
            M.SetItem(X[0], X[1], 1);
            M.SetItem(X[1], X[0], 1);
        }

        // B logikai tömb feltöltése azzal, hogy van-e ott kamera.
        NB = 0;
        for (I = 0; I < N; I++) {
            M_ = M.Minor(I, I);
            B[I] = !bConnected(M_);
            if (B[I])
                NB++;
        }
        fprintf(OF, "City map #%d: %d cameras found\n", ++NN, NB);
        for (I = 0; I < N; I++)
            if (B[I])
                fprintf(OF, "%s ", Names[I]);
        fprintf(OF, "\n\n");
    }
    fclose(IF);
    fclose(OF);
    return 0;
}

// Mélységi bejárás, és összefüggőség vizsgálata
// A mátrix logikai tömb, hogy két csúcs össze van-e kötve.
int bConnected (const cMatrix & G) {
    // B tömb tárolja azt, hogy a csúcsokat megnéztük-e már.
    int I, N = G.GetN(), * B = new int [N], Q = 1;

    for (I = 0; I < N; I++)
        B[I] = 0;
    Recursion(G, 0, B);
    for (I = 0; I < N; I++)
        if (!B[I])
            Q = 0;
    delete [] B;
    return Q;
}
// Mélységi bejárás által használt rekurzió
void Recursion (const cMatrix & G, int X, int * B) {
    for (int I = 0; I < G.GetN(); I++)
        // A még nem felhasznált szomszédokra hívja meg önmagát
        if (!B[I] && G.GetItem(X, I)) {
            B[I] = 1;
            Recursion(G, I, B);
        }
}
(Vissza)