#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<iomanip>
using namespace std;

void sayiDoldur(int metin[][10]){
	for(int i =0;i<10;i++){
		for(int j = 0; j<10;j++){
			metin[i][j]= i*10+j;
		}
	}
}

void sifirla(int dizi[][10]){
	for(int i =0;i<11;i++){
		for(int j = 0; j<10;j++){
			dizi[i][j]= 0;
		}
	}
}

void karistir(int metin[][10]){
	for(int i = 0;i<100;i++){
		int x1 = rand()%10;
		int y1 = rand()%10;
		
		int x2 = rand()%10;
		int y2 = rand()%10;
	
		int temp = metin[x1][y1];
		metin[x1][y1] = metin[x2][y2];
		metin[x2][y2] = temp;
	}
}



void karsilastirici(int metin[][10],int min[][10] ,int konum){
	int ikonum = konum/10; 
	int jkonum = konum%10;
	
	int iust = ikonum-1;
	int just = jkonum;
	
	int isol = ikonum;
	int jsol = jkonum-1;
	
	
	if(ikonum==0&&jkonum==0){
		min[ikonum][jkonum] = metin[ikonum][jkonum];
	}
	
	else if(jkonum==0){
		min[ikonum][jkonum] = min[iust][just]+metin[ikonum][jkonum];
	}
	
	else if(ikonum==0){
		min[ikonum][jkonum] = min[isol][jsol]+metin[ikonum][jkonum];
	}
	
	else{
		
		if(min[iust][just]+metin[ikonum][jkonum] < min[isol][jsol]+metin[ikonum][jkonum]){
			min[ikonum][jkonum] = min[iust][just]+metin[ikonum][jkonum];
		}
		
		else{
			min[ikonum][jkonum] = min[isol][jsol]+metin[ikonum][jkonum];
		}
	}
}


void minyolbulma(int dizi[][10],int min[][10]){
	
	for(int i=0;i<100;i++){
		karsilastirici(dizi,min,i);
	}
	
}

void izbulucu(int dizi[][10],int min[][10],int yol[][10]){
	
	for(int i = 0;i<10;i++){
		for(int j =0;j<10;j++){
			yol[i][j] = dizi[i][j];
		}
	}
	
	int ikonum = 9;
	int jkonum = 9;
	
	for(int i = 0;i<19;i++){
		yol[ikonum][jkonum] = min[ikonum][jkonum]-dizi[ikonum][jkonum];
		
		int s = 111;
		int a = 222;
		int o = 999;
		
		if(ikonum==0&&jkonum==0){
			yol[ikonum][jkonum]=o;
		}
		else if(ikonum==0){
			yol[ikonum][jkonum]=s;
			jkonum -= 1;
		}
		else if(jkonum==0){
			yol[ikonum][jkonum]=a;
			ikonum -= 1;
		}
		else{
			if(yol[ikonum][jkonum] == min[ikonum-1][jkonum]){
				yol[ikonum][jkonum] = a;
				ikonum -= 1;
			}
			else if(yol[ikonum][jkonum] == min[ikonum][jkonum-1]){
				yol[ikonum][jkonum] = s;
				jkonum -= 1;
			}
		}
	}
}

void sonuc(int yol[][10],int dizi[][10],int min[][10]){
	
	cout<<"En kisa yolun maliyeti = "<<min[9][9]<<endl;
	cout<<"--------------------------------------------------"<<endl;
	for(int i = 0;i<10;i++){
		for(int j = 0;j<10;j++){
			
			if(yol[i][j]==111){
				cout<<setw(5)<<dizi[i][j];
			}
			else if(yol[i][j]==222){
				cout<<setw(5)<<dizi[i][j];
			}
			else if(yol[i][j]==999){
				cout<<setw(5)<<dizi[i][j];
			}
			else{
				cout<<setw(5)<<" ";
			}
		}
		cout<<endl;
	}
	
	cout<<"--------------------------------------------------"<<endl;
	
	for(int i = 0;i<10;i++){
		for(int j = 0;j<10;j++){
			
			if(yol[i][j]==111){
				cout<<setw(5)<<"[>]";
			}
			else if(yol[i][j]==222){
				cout<<setw(5)<<"[v]";
			}
			else if(yol[i][j]==999){
				cout<<setw(5)<<"( )";
			}
			else{
				cout<<setw(5)<<dizi[i][j];
			}
		}
		cout<<endl;
	}
	
	cout<<"--------------------------------------------------"<<endl;
}

void printArry(int dizi[][10]){
	for(int i =0;i<10;i++){
		for(int j = 0; j<10;j++){
			cout<<setw(5)<<dizi[i][j];
		}
		cout<<endl;
	}
	cout<<"--------------------------------------------------"<<endl;
}

int main(){
	int dizi[10][10];
	int mindizi[10][10];
	int yoldizi[10][10];
	
	srand(time(0));
	
	bool anahtar=1;
	char input;
	while(anahtar){
		sifirla(mindizi);
		sifirla(yoldizi);
		sayiDoldur(dizi);
		karistir(dizi);
	
		cout<<"++++++++++++++++++++++++++++++++++++++++++++++++++"<<endl;
		cout<<"Yeni Random Yol"<<endl;
		cout<<"--------------------------------------------------"<<endl;
	
		printArry(dizi);
		minyolbulma(dizi,mindizi);
		izbulucu(dizi,mindizi,yoldizi);
		sonuc(yoldizi,dizi,mindizi);
		
		cout<<"Yeniden Oynatmak Istiyorsaniz 1 ,"<<endl;
		cout<<"Istemiyorsaniz 2 basin = ";
		cin>>input;
		
		if(input=='2'){
			anahtar =0;
		}
		else if(input=='1'){
			system("cls");
			anahtar =1;
		}
	}
	return 0;
}