Решение задачи №128 «Один конь» с ACMP

Условие задачи

На шахматной доске N×N в клетке (x1,y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2,y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Входные данные
Входной файл INPUT.TXT содержит пять чисел: N, x1, y1, x2, y2 (5 ≤ N ≤ 20, 1 ≤ x1, y1, x2, y2 ≤ N). Левая верхняя клетка доски имеет координаты (1,1), правая нижняя - (N,N).

Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести наименьшее число ходов коня.

Решение на C++


    #include<iostream>

#include<queue>

using namespace std;

int main() {

	int n,i,j,k,x1,y1,x2,y2,u,v;queue<pair<int,int>>q;

	int x[8]={-2,-2,-1,-1,1,1,2,2},

		y[8]={-1,1,-2,2,-2,2,-1,1};

	cin>>n;int d[n+1][n+1];

	for(i=0;i<=n;++i)

		for(j=0;j<=n;++j)d[i][j]=1000000000;

	cin>>x1>>y1>>x2>>y2;

	d[x1][y1]=0; q.push(make_pair(x1,y1));

	while(!q.empty()){

		i=q.front().first;j=q.front().second;q.pop();

		for(k=0;k<8;++k){u=i+x[k];v=j+y[k];

			if(u>0&&u<=n&&v>0&&v<=n&&d[u][v]>d[i][j]+1){

			d[u][v]=d[i][j]+1;q.push(make_pair(u,v));}}}

	cout<<d[x2][y2];

	return 0;}

Условия задач взяты с сайта acmp.ru