#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

struct Route
{
	string r;
	bool visited;

	Route()
	{
		r = "";
		visited = false;
	}
};

string convertToCell(int x, int y)
{
	string s;
	s += (char)(y + 'A');
	s += (char)(x + '0' + 1);
	return s;
}

void findRoutes(Route** field, int x, int y, string path)
{
	field[x][y].visited = true;
	field[x][y].r = path;

	if (y <= 6 && x >= 2 && (!field[x - 2][y + 1].visited || field[x - 2][y + 1].r.size() > path.size()) )
	{
		findRoutes(field, x - 2, y + 1, path + "1");
	}

	if (y <= 5 && x >= 1 && (!field[x - 1][y + 2].visited || field[x - 1][y + 2].r.size() > path.size()))
	{
		findRoutes(field, x - 1, y + 2, path + "2");
	}

	if (y <= 5 && x <= 6 && (!field[x + 1][y + 2].visited || field[x + 1][y + 2].r.size() > path.size()))
	{
		findRoutes(field, x + 1, y + 2, path + "3");
	}

	if (y <= 6 && x <= 2 && (!field[x + 2][y + 1].visited || field[x + 2][y + 1].r.size() > path.size()))
	{
		findRoutes(field, x + 2, y + 1, path + "4");
	}

	if (y >= 1 && x >= 2 && (!field[x - 2][y - 1].visited || field[x - 2][y - 1].r.size() > path.size()))
	{
		findRoutes(field, x - 2, y - 1, path + "5");
	}

	if (y >= 2 && x >= 1 && (!field[x - 1][y - 2].visited || field[x - 1][y - 2].r.size() > path.size()))
	{
		findRoutes(field, x - 1, y - 2, path + "6");
	}

	if (y >= 1 && x <= 5 && (!field[x + 2][y - 1].visited || field[x + 2][y - 1].r.size() > path.size()))
	{
		findRoutes(field, x + 2, y - 1, path + "7");
	}

	if (y >= 2 && x <= 6 && (!field[x + 1][y - 2].visited || field[x + 1][y - 2].r.size() > path.size()))
	{
		findRoutes(field, x + 1, y - 2, path + "8");
	}

}


int main()
{
	setlocale(LC_ALL, "russian");
	cout << "Введите исходную клетку" << endl;
	string s;
	cin >> s;

	pair<int, int> start = {s[1] - '0' - 1 , s[0] - 'A' };

	cout << "Введите конечную клетку" << endl;

	cin >> s;

	pair<int, int> finish = { s[1] - '0' - 1 , s[0] - 'A' };

	Route** field = new Route*[8];
	for (int i = 0; i < 8; i++)
	{
		field[i] = new Route[8];
	}

	findRoutes(field, start.first, start.second, "");


	cout <<"Количество ходов в полученном пути: "<< field[finish.first][finish.second].r.size() << endl;

	Route result = field[finish.first][finish.second];

	int x = start.first;
	int y = start.second;
	cout << "Путь:\n" << convertToCell(x, y) << " ";
	for (int i = 0; i < result.r.size() - 1; i++)
	{
		switch (result.r[i])
		{
		case '1':
			x -= 2;
			y += 1;
			break;
		case '2':
			x -= 1;
			y += 2;
			break;
		case '3':
			x += 1;
			y += 2;
			break;
		case '4':
			x += 2;
			y += 1;
			break;
		case '5':
			x -= 2;
			y -= 1;
			break;
		case '6':
			x -= 1;
			y -= 2;
			break;
		case '7':
			x += 2;
			y -= 1;
			break;
		case '8':
			x += 1;
			y -= 2;
			break;
		}
		cout << convertToCell(x, y) << " ";
	}
	cout << convertToCell(finish.first, finish.second);
	system("pause>>void");
    return 0;
}