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

#include <iostream>
#include <cmath>
#include "lstack.cpp"
#include "lqueue.cpp"
//#include "sstack.cpp"

using namespace std;

const int MAX = 3;

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

void printBoard() {
	for(int i = 0; i < MAX; i++) {
		for(int j = 0; j < MAX; j++)
			cout << board[i][j] << '\t';
		cout << endl;
	}
	cout << endl;
}

struct Move {
	int sx, sy, move;
};

typedef LStack<Move> MoveStack;

bool horse_stack(int sx, int sy) {
	MoveStack s;
	Move m = { sx, sy, 1 };
	s.push(m);
	int oldMove = 1;
	// симулираме първото извикване на horse
	while(oldMove < MAX * MAX + 1 // условие за приключване с true
			&&
		  s.top(m) // условие за приключване с false
		  ) {
		if (m.move < oldMove) {
			// backtracking!!!
			s.pop(m);
			board[m.sx][m.sy] = 0;
		} else {
			if (m.sx >= 0 && m.sy >= 0 && m.sx < MAX && m.sy < MAX &&
				board[m.sx][m.sy] == 0) {
				board[m.sx][m.sy] = m.move;
				for(int dx = -2; dx <= 2; dx++)
					if (dx != 0)
						for(int dy = -1; dy <= 1; dy += 2) {
							Move n = { m.sx + dx,
									   m.sy + dy * (abs(dx) - 3),
									   m.move + 1 };
							s.push(n);
						}
			} else
				s.pop(m);
		}
		oldMove = m.move;
	}
	return !s.empty();
	// return m.move == MAX * MAX;
}

bool horse_recursive(int sx, int sy, int move) {
	if (sx < 0 || sy < 0 || sx >= MAX || sy >= MAX)
		return false;
	if (board[sx][sy] != 0)
		return false;
	board[sx][sy] = move++;
	// printBoard();
	if (move == MAX * MAX + 1)
		return true;
	for(int dx = -2; dx <= 2; dx++)
		if (dx != 0)
			for(int dy = -1; dy <= 1; dy += 2)
				if (horse_recursive
						(sx + dx,
						 sy + dy * (abs(dx) - 3),
						 move))
					return true;
					/*
	if (horse_recursive(sx + 2, sy + 1, move) ||
		horse_recursive(sx + 2, sy - 1, move) ||
		horse_recursive(sx - 2, sy + 1, move) ||
		horse_recursive(sx - 2, sy - 1, move) ||
		horse_recursive(sx + 1, sy + 2, move) ||
		horse_recursive(sx + 1, sy - 2, move) ||
		horse_recursive(sx - 1, sy + 2, move) ||
		horse_recursive(sx - 1, sy - 2, move))
		return true;
		*/
	board[sx][sy] = 0;
	return false;
}

void horse_queue(int sx, int sy, int ex, int ey) {
	LQueue<Move> q;
	Move m = { sx, sy, 1 };
	q.push(m);
	while (q.pop(m) && (m.sx != ex || m.sy != ey)) {
		if (m.sx >= 0 && m.sy >= 0 && m.sx < MAX && m.sy < MAX &&
			board[m.sx][m.sy] == 0) {
			board[m.sx][m.sy] = m.move;
			for(int dx = -2; dx <= 2; dx++)
				if (dx != 0)
					for(int dy = -1; dy <= 1; dy += 2) {
						Move n = { m.sx + dx,
								   m.sy + dy * (abs(dx) - 3),
								   m.move + 1 };
						q.push(n);
					}
		}
	}
	if (m.sx == ex && m.sy == ey)
		board[ex][ey] = m.move;
	else
		cout << "Няма решение!" << endl;
	printBoard();
}

int main() {
	/*
	 if (horse_stack(0, 0))
		printBoard();
	else
		cout << "Няма ход на коня!\n";
		*/
	horse_queue(0, 0, 1, 1);
	return 0;
}