Zaimplementuj zachłanny algorytm poszukiwania drogi w podanej tablicy. Dane podane są w pliku wejściowym dane.txt. W pliku znajduje się liczba N oraz tablica liczb nieujemnych, całkowitych o wymiarach N x N. Program, z użyciem metody zachłannej, znajduje drogę z lewego dolnego rogu tablicy do prawego górnego rogu i jej koszt. Program wypisuje do pliku wynik.txt współrzędne kolejnych pól na drodze w tablicy. Po tablicy możemy poruszać się tylko do góry lub w prawo.
Przykład
Plik wejściowy dane.txt
5
2 3 4 2 5
5 2 1 2 2
2 4 2 2 3
1 2 2 4 3
3 2 1 2 3
Przykładowe wyjście (może się różnić, w zależności od implementacji) - plik wynik.txt
Koszt: 22
4 0
3 0
2 0
2 1
1 1
1 2
1 3
0 3
0 4
Co zmienić w algorytmie żeby działał jak w poleceniu?
#include <iostream>
#include<fstream>
#include<string>
int main()
{
using namespace std;
string tekst;
fstream plik("dane.txt");
if(plik.is_open())
{
int size;
plik >> size;
cout << "wczytana wielkosc tablicy: " << size;
{
while(plik.good())
{
getline(plik, tekst);
cout << tekst << endl;
}
plik.close();
}
}
else
{
cout << "Blad otwarcia pliku dane.txt!";
{
int n;
int i,j;
int G[n-1-1][0];
int P[n-1][1];
int D[n-1][0];
int liczba[5][5];
ifstream plik("dane.txt");
for(int i = 0; i < 5; i++)
for(int j = 0; j < 5; j++)
plik >> liczba[i][j];
for(int i = 0; i < 5; i++)
{
for(int j = 0; j < 5; j++)
cout << liczba[i][j] << " ";
cout << "\n";
}
i=0;
for(j=1;j<n+1;j++)
{
D[i][j]=D[i][j-1]+P[i][j-1];
}
for(i=1;i<n+1;i++){
D[i][0]=D[i-1][0]+G[i-1][0];
for(j=1;j<n+1;j++)
{
if(D[i-1][j]+G[i-1][j]<D[i][j-1]+P[i][j-1])
{
D[i][j] = D[i-1][j] + G[i-1][j];
}
else
{
D[i][j] = D[i][j-1] + P[i][j-1];
}
}
}
for(i=n;i>=0;i--){
for(j=0;j<n+1;j++)
{
cout << D[i][j] <<" ";
}
cout << endl;
}
ofstream plik;
plik.open("wynik.txt");
plik << "Przykladowy tekst";
plik.close();
}
}
return 0;
}``