fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. // Клетка шахматной доски
  7. struct cell {
  8. 	int a;	// Вертикальная координата (числа)
  9. 	int b;	// Горизонтальная координата (буквы)
  10. 	int d;	// Расстояние до этой клетки из начальной
  11. }; 
  12.  
  13. // Узел. Используется в очереди
  14. struct node {
  15. 	cell val;
  16. 	node *next;
  17. 	node(cell v, node *n = NULL) {
  18. 		val = v;
  19. 		next = n;
  20. 	}
  21. };
  22.  
  23. // Очередь. Используется для поиска в ширину
  24. struct Queue {
  25. 	node *head;
  26. 	Queue(node *h = NULL) {
  27. 		head = h;
  28. 	}
  29. 	void push(cell v) {	// Добавить элемент в очередь
  30. 		head = new node(v, head);
  31. 	}
  32. 	cell pop() {	// Изъять элемент из очереди
  33. 		if((head -> next) != NULL) {
  34. 			node *i = head;
  35. 			node *p = i;
  36. 			while(i -> next != NULL) {
  37. 				p = i;
  38. 				i = i -> next;
  39. 			}
  40. 			cell v = i -> val;
  41. 			p -> next = NULL;
  42. 			delete i;
  43. 			return v;
  44. 		} else {
  45. 			node *n = head;
  46. 			cell v = head -> val;
  47. 			head = head -> next;
  48. 			delete n;
  49. 			return v;
  50. 		}
  51. 	}
  52. 	void clear() {	// Очистить очередь
  53. 		head = NULL;
  54. 	}
  55. };
  56.  
  57. int main() {
  58. 	string r;	// Строка для запроса
  59. 	Queue q;	// Очередь
  60. 	cell current, goal, next;	// Текущая, конечная и следующая клетки
  61. 	bool visited[8][8];	// Посещенные клетки
  62. 	while(getline(cin, r)) {
  63.  
  64. 		// Готовим текущую и конечную клетки
  65. 		current.a = (int)(r[1] - '1');
  66. 		current.b = (int)(r[0] - 'a');
  67. 		goal.a = (int)(r[4] - '1');
  68. 		goal.b = (int)(r[3] - 'a');
  69. 		current.d = 0;
  70.  
  71. 		// Готовим массив посещенных клеток
  72. 		for(int i = 0; i < 8; i++)
  73. 			for(int j = 0; j < 8; j++)
  74. 				visited[i][j] = false;
  75. 		visited[current.a][current.b] = true;
  76.  
  77. 		// Готовим очередь
  78. 		q.push(current);
  79.  
  80. 		// Выполняем поиск в ширину
  81. 		while( !(current.a == goal.a && current.b == goal.b) ) {	// Пока координаты очередной клетки из очереди не совпадут с координатами конечной
  82. 			current = q.pop();	// Достаем новую клетку из очереди
  83. 			next.d = current.d + 1;	// Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего
  84. 			// Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам
  85. 			for(int i = -2; i <= 2; i++)	
  86. 				if(i != 0)
  87. 					for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) {
  88. 						// Присваиваем следующей клетке новые координаты
  89. 						next.a = current.a + i;
  90. 						next.b = current.b + j;
  91. 						if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) {	// Если следующая клетка находится в пределах доски и не была посещена
  92. 							q.push(next);	// Добавляем ее в очередь
  93. 							visited[next.a][next.b] = true;	// Отмечаем ее посещенной
  94. 						}
  95. 					}
  96. 		}
  97.  
  98. 		// Выводим ответ
  99. 		cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl;
  100.  
  101. 		// Очищаем очередь для следующего теста
  102. 		q.clear();
  103. 	}
  104. 	return 0;
  105. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
stdout
copy 
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
https://ideone.com/mItCA1
Шахматная доска (норм)
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!