#include "Func.h"
int find_best_path() {
	int** a,** b;
	int rows , cols = 0;
	cout << "Nhap so hang\n";
	cin >> rows;
	cout << "Nhap so cot\n";
	cin >> cols;
	a = new int* [rows] {nullptr};
	b = new int* [rows] {nullptr};
	for (int i = 0; i < rows; i++) {
		a[i] = new int[cols] {0};
		b[i] = new int[cols] {0};
	}
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			cout << "NHap phan tu tai vi tri [ " << i << " ] [ " << j << " ] : ";
			cin >> a[i][j];


		}
	}
	cout << "Map is :\n";
	for (int i = rows - 1; i >= 0; i--) {
		
		for (int j = 0; j < cols; j++) {

			cout << " " << a[i][j];


		}
		cout << endl;
	}
	for (int i = 0; i < cols; i++) {
		b[0][i] = a[0][i];
	}
	for (int i = 1; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (j == 0) {
				b[i][j] = (b[i - 1][j] > b[i - 1][j + 1] ? b[i - 1][j] : b[i - 1][j + 1]) + a[i][j];
			}
			else if (cols - 1 == j) {
				b[i][j] = (b[i - 1][j] > b[i - 1][j - 1] ? b[i - 1][j] : b[i - 1][j - 1]) + a[i][j];
			}
			else {
				int temp = b[i - 1][j] > b[i - 1][j + 1] ? b[i - 1][j] : b[i - 1][j + 1];
				b[i][j] = (b[i - 1][j - 1] > temp ? b[i - 1][j - 1] : temp) + a[i][j];
			}
		}
	}
	int MAX = INT_MIN;
	int x = 0;

	for (int i = 0; i < rows; i++) {
		if (b[cols - 1][i] > MAX) {
			MAX = b[cols - 1][i];
			x = i;
		}
	}
	//cout << x << endl;
	int* arr = new int[rows];
	arr[0] = x;
	for (int i = rows - 2; i >= 0; i--) {
		
		if (x == 0) {
			arr[rows - 1 - i] = b[i][x] > b[i][x + 1] ? x : (x + 1);
		}
		else if (cols - 1 == i) {
			arr[rows - 1 - i] = b[i][x] > b[i][x - 1] ? x : (x - 1);

		}
		else {
			int temp = b[i][x] > b[i][x + 1] ? b[i][x] : b[i][x + 1];
			int temp1 = b[i][x] > b[i][x + 1] ? x : x + 1;
			arr[rows - 1 - i] = b[i][x - 1] > temp ? (x - 1) : temp1;
		}
	}
	for (int i = rows - 1; i >= 0; i--) {
		
		cout << " [ " << rows - 1 - i << " ] [ " << arr[i] << " ]  ";
		if (i != 0) {
			cout << " --> ";
		}
	}
	cout << endl;
	return MAX;




}