Cautare A*

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>


using namespace std;

int a[20][20];
int vizitat[20];

void Afisare() {
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}
void main() {
    char *nume[20] = { "Arad","Bucuresti","Craiova", "Drobeta","Eforie","Fagarasi","Giurgiu","Hirsova","Iasi","Lugoj","Mehadia","Neamt","Oradea","Pitesti","Rimnicu Valcea","Sibiu","Timisoara","Urziceni","Vaslui","Zerind" };
    // 0          1          2          3         4          5         6      7         8       9       10     11       12       13         14            15       16          17         18        19
    int noduri[20];
    int nr_noduri = 0;
    int n = 20;
    int oras_Start = 12, oras_Destinatie = 1;
    int adancime[20];               //stocheaza adancimea fiecarui nod //
    int limita = 15;
    int solutie[20];
    int parinte[20];
    int nr_solutie = 0;
    int cost[20];
    int h[20] = { 366,0,160,242,161,176,77,151,226,244,241,234,380,101,193,253,329,80,199,374 };
    //euristica ,vector ce reprezinta distantele in linie dreapta pan ala bucuresti
    /*
    cout << "Introduceti oras start: \n";
    cin >> oras_Start;

    cout << "Introduceti oras destinatie: \n";
    cin >> oras_Destinatie;
    */
    const int o_Destinatie = oras_Destinatie;
    a[0][16] = 118;
    a[0][15] = 140;
    a[0][19] = 75;
    a[1][5] = 211;
    a[1][6] = 90;
    a[1][13] = 101;
    a[1][17] = 85;
    a[2][3] = 120;
    a[2][13] = 138;
    a[2][14] = 146;
    a[3][10] = 75;
    a[4][7] = 86;
    a[5][15] = 99;
    a[7][17] = 98;
    a[8][11] = 87;
    a[8][18] = 92;
    a[9][10] = 70;
    a[9][16] = 111;
    a[12][19] = 71;
    a[12][15] = 151;
    a[13][14] = 97;
    a[14][15] = 80;
    a[17][18] = 142;

    /*a[0][16] = 1;
    a[0][15] = 1;
    a[0][19] = 1;
    a[1][5] = 1;
    a[1][6] = 1;
    a[1][13] = 1;
    a[1][17] = 1;
    a[2][3] = 1;
    a[2][13] = 1;
    a[2][14] = 1;
    a[3][10] = 1;
    a[3][2] = 1;
    a[4][7] = 1;
    a[5][1] = 1;
    a[5][15] = 1;
    a[7][17] = 1;
    a[8][11] = 1;
    a[8][18] = 1;
    a[9][10] = 1;
    a[9][16] = 1;
    a[12][19] = 1;
    a[12][15] = 1;
    a[13][14] = 1;
    a[14][15] = 1;
    a[17][18] = 1;*/
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            a[j][i] = a[i][j];

        }
    }


    //cout << "Afisare" << endl;
    //  Afisare();
    //  int cautare;
    //  cout << "Introduceti indicele orasului caruia vreti sa ii aflam vecinii: "; cin >> cautare;cout << endl;
    //  cout << nume[cautare] << " are vecinii:" << endl;
    //  for (int i = 0;i < 20;i++)
    //      if (a[cautare][i] == 1) {
    //          cout << nume[i] << " ";
    //      }
    // CAUTAREA CU COST UNIFORM

    noduri[0] = oras_Start;
    nr_noduri++;
    vizitat[oras_Start] = 1;
    cost[oras_Start] = 0;
    int gasit = 0;
    int nod;//nodul curent pe care il initializam
    while (gasit == 0 && (nr_noduri != 0)) {

        nod = noduri[0];//scoatem primul element din lista de noduri si il retinem in noduri
        for (int i = 0; i < nr_noduri - 1; i++) {
            noduri[i] = noduri[i + 1];
        }
        nr_noduri--;

        if (nod == oras_Destinatie) {
            gasit = 1;
        }
        else {
            for (int i = 0; i < 20; i++) {
                if ((a[nod][i] != 0) && ((vizitat[i] == 0) || ((vizitat[i] == 1) && (cost[i] >  cost[nod] + a[nod][i])))) {//orasele conectate de nod && nevizitate
                                                                                                                           // costul vechi e mai mare decat noul cost
                                                                                                                           //  orasele conectate de nod SI (fie sunt nevizitate , fie au fost vizitate) dar la o adancime mai mare decat adancimea PE care ar primi-o acum
                                                                                                                           //
                    cost[i] = cost[nod] + a[nod][i];
                    int j = 0;
                    while ((j < nr_noduri) && (cost[i]+h[i] >cost[noduri[j]]+ h[noduri[j]])) {
                        j++;// j va fi pozitia PE care inserez in lista de noduri
                    }
                    for (int k = nr_noduri; k > j; k--) { // Adaug acel i astfel incat lista sa fie ordonata crescator dupa cost
                        noduri[k] = noduri[k - 1]; // noduri[i-1] si asta in loc de a mai pune i-- la for
                    }
                    noduri[j] = i; // aceste 3 linii se modifica la cautarea in latime
                    nr_noduri++;
                    vizitat[i] = 1;
                    parinte[i] = nod;
                    adancime[i] = adancime[nod] + 1;
                }
            }
        }
    }

    int c = cost[oras_Destinatie];
    if (gasit == 0) {
        cout << "\nNu s-a gasit\n\n";
    }
    else {

        while (oras_Destinatie != oras_Start) {
            solutie[nr_solutie++] = oras_Destinatie;
            oras_Destinatie = parinte[oras_Destinatie];
        }
        solutie[nr_solutie] = oras_Start;


        cout << "\nDrumul  dintre " << nume[oras_Start] << " si " << nume[o_Destinatie] << " este\n";

        for (int i = nr_solutie; i >= 0; i--) {
            cout << nume[solutie[i]] << " ";
        }
        cout << endl << "Lungimea drumului este: " << c;
    }
    _getch();
}