/*
 * horse.cpp
 *
 *  Created on: 07.11.2012
 *      Author: trifon
 */

#include <iostream>
#include <cmath>
using namespace std;
#include "lstack.cpp"

const int MAX = 8;

bool board[MAX][MAX] = { 0 };

struct Move
{
	int x, y;
	int moves;
};

int horse_moves_iter(int sx, int sy, int ex, int ey,
						int moves)
{
	LStack<Move> sm;
	Move m = { sx, sy, moves };
	sm.push(m);

	while(sm.pop(m) && (m.x != ex || m.y != ey))
	{
		if (!(m.x < 0 || m.y < 0 || m.x >= MAX || m.y >= MAX)
			 &&
			 !board[m.x][m.y])
		{
			board[m.x][m.y] = true;
			for(int x = -2; x <= 2; x++)
				if (x != 0)
					for (int y = -(3-abs(x)); y < 3; y += 2*abs(y))
					{
						Move n = { m.x + x, m.y + y, m.moves + 1 };
						sm.push(n);
					}
		}
	}
	return m.moves;
}

int horse_moves_rec(int sx, int sy,
					  int ex, int ey, int moves)
{
	if (sx < 0 || sy < 0 || sx >= MAX || sy >= MAX)
		return -1;
	if (board[sx][sy])
		return -1;
	if (sx == ex && sy == ey)
		return moves;
	board[sx][sy] = true;
	for(int x = -2; x <= 2; x++)
		if (x != 0)
			for (int y = -(3-abs(x)); y < 3; y += 2*abs(y))
			{
				int m = horse_moves_rec(sx + x, sy + y,
										 ex, ey, moves+1);
				if (m != -1)
					return m;
			}
	return -1;
}

int main()
{
	int sx, sy, ex, ey;
	cout << "Въведете начална позиция: ";
	cin >> sx >> sy;
	cout << "Въведете крайна позиция: ";
	cin >> ex >> ey;
	cout << "Конят може да се премести за "
			<< horse_moves_iter(sx, sy, ex, ey, 0) << " хода."
			<< endl;
}