#include <iostream>
#include <iterator>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

struct Position
{
    int x;
    int y;
    short b_used:1;
    bool operator <(const Position& right) const;
    bool operator==(const Position& right) const;
};
bool Position::operator <(const Position& right) const
{
    if (x < right.x)
    {
        return true;
    }
    else if (x == right.x)
    {
        if (y < right.y)
        {
            return true;
        }
    }
    return false;
}
bool Position::operator==(const Position& right) const
{
    if (x == right.x && y == right.y)
    {
        return true;
    }
    return false;
}
class ChessHorse
{
public:
    /**
    * 
    **/
    ChessHorse(int t_n,int t_m)
        :n(t_n),
        m(t_m)
    {
        deriction = 8;  /*共有8个方向*/
        SetPos poss;
        ChessBoardCol chess_board_col(m,poss);
        chess_board_path = ChessBoardPath(n,chess_board_col);
        init_path();
        VecInt cols(m);
        chess_board = ChessBoard(n,cols);
        found_count = 0;
    }
    ~ChessHorse()
    {
        return;
    }
    /**
     * 初始化路径值
     */
    int init_path()
    {
        for (int i = 0;i < n;i ++)
        {
            for (int j = 0;j < m;j ++)
            {
                for (int deriction = 1;deriction <= 8;deriction ++)
                {
                    int x = i;
                    int y = j;
                    switch (deriction)
                    {
                        case 1: x += 1;  y += 2; break;
                        case 2: x += 1;  y -= 2; break;
                        case 3: x -= 1;  y += 2; break;
                        case 4: x -= 1;  y -= 2; break;
                        case 5: x += 2;  y += 1; break;
                        case 6: x += 2;  y -= 1; break;
                        case 7: x -= 2;  y += 1; break;
                        case 8: x -= 2;  y -= 1; break;
                        default: return -1;
                    }
                    if (check(x,y) == false)
                    {
                        continue;
                    }
                    Position pos;
                    pos.x = x;
                    pos.y = y;
                    pos.b_used = 0;
                    SetPos &poss = chess_board_path[i][j];
                    poss.insert(pos);
                }
            }
        }
        return 1;
    }
    bool check(int x,int y)
    {
        if (x >= n || x < 0 || y >= m || y < 0)
        {
            return false;
        }
        return true;
    }
    /**
     * x,y起始坐标
     */
    int search(int x,int y,int dep)
    {
        SetPos &poss = chess_board_path[x][y];

        Position pos;
        pos.x = x;
        pos.y = y;
        chess_board[x][y] = dep;

        //print_table();
        if (dep == n * m)
        {
            cout << "found:" << endl;
            print_table();
            cout << "--------------" << endl;
            found_count ++;
            return 1;
        }
        if (poss.empty() == true)
        {
            //无路可走
            return 0;
        }

        for (SetPos::iterator iter = poss.begin();
            iter != poss.end();++iter)
        {
            x = iter->x;
            y = iter->y;
            SetPos& t_poss = chess_board_path[x][y];
            t_poss.erase(pos);
        }
        for (SetPos::iterator iter = poss.begin();
            iter != poss.end();++iter)
        {
            short b_used = iter->b_used;
            if (b_used == 1)
            {
                continue;
            }
            x = iter->x;
            y = iter->y;
            SetPos &t_poss = chess_board_path[x][y];
            search(x,y,dep + 1);
        }
        for (SetPos::iterator iter = poss.begin();
            iter != poss.end();++iter)
        {
            x = iter->x;
            y = iter->y;
            SetPos& t_poss = chess_board_path[x][y];
            t_poss.insert(pos);
        }
        chess_board[x][y] = 0;
        return 1;
    }
    /**
     * 
     */
    void print_table()
    {
        ChessBoard::iterator iter = chess_board.begin();
        for (;iter != chess_board.end();++iter)
        {
            VecInt cols = *iter;
            VecInt::iterator iter_col = cols.begin();
            for (;iter_col != cols.end();++iter_col)
            {
                cout << *iter_col << "\t";
            }
            cout << endl;
        }
    }
    int get_found_count()
    {
        return found_count;
    }
protected:
    int n,m;
    int deriction;
    typedef vector<Position> VecPos;
    typedef set<Position> SetPos;
    typedef vector<SetPos> ChessBoardCol;
    typedef vector<ChessBoardCol> ChessBoardPath;
    typedef vector<int> VecInt;
    typedef vector<VecInt> ChessBoard;

    ChessBoard chess_board;
    ChessBoardPath chess_board_path;
    int found_count;
private:
};
int main()
{
    ChessHorse chess_horse(4,3);
    chess_horse.search(0,1,1);
    cout << "total found:" << chess_horse.get_found_count() << endl;

    return 0;
};