Chess.cpp

#include <iostream>
#include <vector>
using namespace std;
struct cell{
	int num;
	char let;
	// для решения создадим структуру шахматной клетки, определённой буквой от А до Н и цифрой от 1 до 8
};
bool operator ==(cell a1, cell a2) {
	if ((a1.let == a2.let) && (a1.num == a2.num)) {//для решения пригодится оператор "равно", возвращающий true, если клетки совпадают
		return true;
	}
	else return false;
}
struct queue {
	cell inf;
	queue* next; //структура очень похожа на стек, даже содержащиеся поля идентичны
};
void push(queue*& h, queue*& t, cell x) {// функция вставки элемента в начало очереди
	//уже можно заметить, что функция похожа на такую у стека, отличается она только тем, что нужно проверку, если очередь пустая
	queue* r = new queue;
	r->inf = x;
	r->next = nullptr;
	if (!h && !t) {//собсна сама проверка, нужно проверить, если оба указателя смотрят в пустоту, то по сути просто изначальную очередь представляем как ту, которую создали для решения
		h = t = r;
	}
	else {//иначе идём также как и со стеком, но в обратную сторону
		t->next = r;
		t = r;
	}
}
cell pop(queue*& h, queue*& t) {//функция удаления первого элемента из очереди, почти полностью идентична таковой из стеков
	queue* r = h;
	cell i = h->inf;
	h = h->next;
	if (!h) t = nullptr;//единственное отличие - это необходимость проверить, если мы вдруг удалили единственный элемент в очереди, то нужно обнулить и второй указатель 
	delete r;
	return i;
}
void print(cell a) {
	cout << a.let << a.num<<" ";//функция вывода координаты клетки на экран
}

int main() {
	//В ходе размышлений, мой великий разум предпринял решение представить шахматную доску, как граф, представленный списком смежности из 64 строк, где каждая строка содержит клетки,
	//в которые может пойти конь из указанной клетки 
	vector <vector <cell>> Gr;//вектор векторов, который и будет представлять список смежности
	cell cur, cand;//клетки cur, для которой и будут искаться остальные клетки, куда может пойти конь (далее "смежные клетки"), и cand - "кандидат" на ту клетку, куда конь может пойти, не выходя за доску 
	cur.let = 'A';
	cur.num = 1;//начнём с самой первой клетки
	for (int i = 0; i < 64; i++) {
		Gr.push_back(vector <cell>());
		//начинаем заполнение списка, для этого для каждой клетки нужно выполнить проверку, не выходят ли её смежные клетки за пределы доски, если нет, то добавляем их в список смежности
		//собственно это в следующих блоках и происходит, надеюсь на не очень сильные удары ногами за следующую кучу кода
		if ((cur.let + 2 >= 'A' && cur.let + 2 <= 'H') && (cur.num + 1 <= 8 && cur.num + 1 >= 1)) {
			cand.let = char(cur.let + 2);
			cand.num = cur.num + 1;
			Gr[i].push_back(cand);
		}
		if ((cur.let + 2 >= 'A' && cur.let + 2 <= 'H') && (cur.num - 1 <= 8 && cur.num - 1 >= 1)) {
			cand.let = char(cur.let + 2);
			cand.num = cur.num - 1;
			Gr[i].push_back(cand);
		}
		if ((cur.let + 1 >= 'A' && cur.let + 1 <= 'H') && (cur.num + 2 <= 8 && cur.num + 2 >= 1)) {
			cand.let = char(cur.let + 1);
			cand.num = cur.num + 2;
			Gr[i].push_back(cand);
		}
		if ((cur.let + 1 >= 'A' && cur.let + 1 <= 'H') && (cur.num - 2 <= 8 && cur.num - 2 >= 1)) {
			cand.let = char(cur.let + 1);
			cand.num = cur.num - 2;
			Gr[i].push_back(cand);
		}
		if ((cur.let - 1 >= 'A' && cur.let - 1 <= 'H') && (cur.num + 2 <= 8 && cur.num + 2 >= 1)) {
			cand.let = char(cur.let - 1);
			cand.num = cur.num + 2;
			Gr[i].push_back(cand);
		}
		if ((cur.let - 1 >= 'A' && cur.let - 1 <= 'H') && (cur.num - 2 <= 8 && cur.num - 2 >= 1)) {
			cand.let = char(cur.let - 1);
			cand.num = cur.num - 2;
			Gr[i].push_back(cand);
		}
		if ((cur.let - 2 >= 'A' && cur.let - 2 <= 'H') && (cur.num + 1 <= 8 && cur.num + 1 >= 1)) {
			cand.let = char(cur.let - 2);
			cand.num = cur.num + 1;
			Gr[i].push_back(cand);
		}
		if ((cur.let - 2 >= 'A' && cur.let - 2 <= 'H') && (cur.num - 1 <= 8 && cur.num - 1 >= 1)) {
			cand.let = char(cur.let - 2);
			cand.num = cur.num - 1;
			Gr[i].push_back(cand);
		}
		if (cur.let < 'H') cur.let = char(cur.let + 1);//выполнив проверку, сдвигаем текущую клетку на следующую 
		else {
			cur.let = 'A';
			cur.num += 1;
		}
	}

	int* a = new int[64];
	for (int i = 0; i < 64; i++)
		a[i] = -1;//также для решения понадобится массив, регистрирующий посещение соответствующей клетки, но здесь не просто будет регистрироваться посещение,
		//вместо этого будет указываться, за сколько минимальное количество ходов можно добраться до какой-то клетки из стартовой 
	queue* h = nullptr;
	queue* t = nullptr;//создаём очередь, которая будет необходима для выполнения обхода в ширину, именно этот обход по графу нам пригодиться для нахождения кратчайшего пути 
	vector <cell> path;//вектор, в который мы запишем пройденный путь 
	cell x, y, z, w;//клетка х - начальная клетка, клетка y - понадобится для обхода в ширину, z - конечная клетка, 
	//w - т.к. в ходе работы клетка x будет меняться, то нужно будет сохранить начальное значение в другой переменной

	bool fl = true;//иногда возможен случай, что из одной в клетки в другую попасть невозможно, для этого создадим булеву переменную, которая укажет на это и, соответственно, прервёт цикл обхода
	int c = 0;//для этого будем считать кол-во сделанных ходов, очевидно, что если программа сделает больше ходов, чем есть клеток на доске, то из клетки х в клетку z попасть невозможно
	bool fin = false;//или если мы всё-таки нашли конечную клетку, то также нужно будет прервать цикл
	cout << "Put coordinates of begin and destination" << endl;
	cin >> x.let;
	cin >> x.num;
	w.let = x.let;
	w.num = x.num;//вводим координаты начальной клетки
	a[x.let - 'A' + 8 * (x.num - 1)] = 0;//и отмечаем одно посещение заданной клетки в массиве а
	//сразу стоит пояснить, что выше указанная формула позволяет однозначно сопоставить текущую клетку с числом из диапазона [0, 63], что будет необходимо, для того, чтобы отметить посещение клетки в массиве а 
	push(h, t, x);//добавляем х в очередь
	cin >> z.let;
	cin >> z.num;//вводим координаты конечной клетки
	path.push_back(z);//и тут же добавляем её для вывода кратчайшего пути
	while (h && !fin && fl) {//и начинаем обход в ширину

		x = pop(h, t);//рассмотрим самый первый в очереди элемент
		for (int i = 0; i < Gr[x.let - 'A' + 8 * (x.num - 1)].size(); i++) {//а затем посмотрим в соответствующей ему строке в списке смежности смежные клетки 
			if (a[Gr[x.let - 'A' + 8 * (x.num - 1)][i].let - 'A' + 8 * (Gr[x.let - 'A' + 8 * (x.num - 1)][i].num - 1)] == -1) {//если текущая клетка не была ни разу посещена,то
				y = Gr[x.let - 'A' + 8 * (x.num - 1)][i];//ну, во-первых, запомним её
				a[y.let - 'A' + 8 * (y.num - 1)] = a[x.let-'A'+8*(x.num-1)]+1;//отметим её посещение в таблице, очевидно, что её расстояние от начальной клетки равно расстоянию извлечённой до этого из очереди клетки плюс один
				push(h, t, y);//затем добавим эту клетку в очередь
				if ((y.let == z.let) && (y.num == z.num))
					fin = true;//если среди этих клеток попалась конечная, то можно прервать цикл
				
			}
		}
		c++;
		if (c >= 64) fl = false;//увеличиваем счётчик с, если клетка не была найдена
	}

	while (!(z == w)) {//далее восстановим путь из конечной клетки в начальную
		if (!fl) {
			cout << "Impossible " << endl;//если цикл обхода был завершён из-за невозможности достижения конечной клетки, то выводим сообщение об этом и прерываем цикл
			break;
		}
		for (int i = 0; i < Gr[z.let - 'A' + 8 * (z.num - 1)].size(); i++) {
			if (a[Gr[z.let - 'A' + 8 * (z.num - 1)][i].let - 'A' + 8 * (Gr[z.let - 'A' + 8 * (z.num - 1)][i].num - 1)] == a[z.let - 'A' + 8 * (z.num - 1)] - 1) {
				//иначе будем вновь смотреть на строку, соответсвующей рассматриваемой клетки, если в этой строке есть смежная клетка, расстояние до которой от начальной клетки меньше на единицу,
				//то именно клетка и нужна была для достижения конечной клетки 
				z = Gr[z.let - 'A' + 8 * (z.num - 1)][i];
				path.push_back(z);//поэтому добавим её в вектор для вывода 
				break;
			}
		}

	}
	cout << "The shortest path is: ";
	reverse(path.begin(), path.end());//перевернём востановленный путь, так как мы шли от конечной клетки к начальной
	for (int i = 0; i < path.size(); i++) print(path[i]);//и выведем его
}