#ifdef _DEBUG
#pragma comment ( lib, "cxcore200d.lib" )
#pragma comment ( lib, "cv200d.lib" )
#pragma comment ( lib, "highgui200d.lib" )
#else
#pragma comment ( lib, "cxcore200.lib" )
#pragma comment ( lib, "cv200.lib" )
#pragma comment ( lib, "highgui200.lib" )
#endif
#include "cv.h"
#include "highgui.h"
#include <iostream>
#include <stdlib .h>
using namespace std;

IplImage* frame = NULL;

#define MAP_MODE 2
#define BLOCK_SIZE 50
#define WINDOW_NAME "Puzzle"
class CPoint
{
    public:
        CPoint(int xx,int yy);
        CPoint(){};
        int x;
        int y;
};

CPoint::CPoint( int xx,int yy )
{
    x = xx;
    y = yy;
}

#if MAP_MODE==1
const int M = 7;  //纵向
const int N = 7;  //横向
const int grey_block_num = 6;
int g_map[M][N] = {
                    {0,1,1,0,0,0,0},
                    {0,1,1,2,2,3,3},
                    {0,1,1,2,2,3,3},
                    {4,4,0,2,2,3,3},
                    {4,4,5,5,6,6,0},
                    {4,4,5,5,6,6,0},
                    {0,0,5,5,6,6,0}
                   };
#endif
#if MAP_MODE==2
const int M = 9;  //纵向
const int N = 9;  //横向
const int grey_block_num = 11;
int g_map[M][N] = {
    {0,0,1,1,2,2,2,0,0},
    {0,0,1,1,2,2,2,3,3},
    {4,4,1,1,5,5,5,3,3},
    {4,4,0,0,5,5,5,3,3},
    {4,4,6,6,6,7,7,8,8},
    {9,9,6,6,6,7,7,8,8},
    {9,9,0,10,10,7,7,8,8},
    {9,9,0,10,10,0,11,11,11},
    {0,0,0,10,10,0,11,11,11}
};
#endif
class CMap
{
    public:
        int map[M][N];
        int block_step[grey_block_num];
        CPoint patch[M*N];
        int Patch_num;
        //CPoint cur_point;
};

void Draw_frame_background()
{
    for(int i = 0;i < frame->height;i++)
    {
        for(int j = 0;j < frame->width;j++)
        {
            CV_IMAGE_ELEM(frame,uchar,i,3*j) =
            CV_IMAGE_ELEM(frame,uchar,i,3*j+1) =
            CV_IMAGE_ELEM(frame,uchar,i,3*j+2) = 255;
        }
    }
    //draw block inside
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < M;j++)
        {
            if (g_map[j][i] != 0)
            {
                cvRectangle(frame,cvPoint(i*BLOCK_SIZE,j*BLOCK_SIZE),cvPoint((i+1)*BLOCK_SIZE,(j+1)*BLOCK_SIZE),cvScalar(128,128,128),CV_FILLED);
            }
        }
    }
    //draw grid
    for(int i = 1;i < M;i++)//纵向
    {
        cvLine(frame,cvPoint(0,i*BLOCK_SIZE),cvPoint(N*BLOCK_SIZE,i*BLOCK_SIZE),cvScalar(200,200,200));
    }
    for(int i = 1;i < N;i++)//横向
    {
        cvLine(frame,cvPoint(i*BLOCK_SIZE,0),cvPoint(i*BLOCK_SIZE,M*BLOCK_SIZE),cvScalar(200,200,200));
    }

    //draw block bounder
    for(int i = 0;i < M;i++)//纵向
    {
        for(int j = 0;j < N-1;j++)
        {
            if (g_map[i][j] != g_map[i][j+1])
            {
                cvLine(frame,cvPoint(BLOCK_SIZE*(j+1),i*BLOCK_SIZE),cvPoint(BLOCK_SIZE*(j+1),(i+1)*BLOCK_SIZE),cvScalar(0,0,0),3);
            }
        }
    }
    for(int i = 0;i < N;i++)//横向
    {
        for(int j = 0;j < M-1;j++)
        {
            if (g_map[j][i] != g_map[j+1][i])
            {
                cvLine(frame,cvPoint(BLOCK_SIZE*i,(j+1)*BLOCK_SIZE),cvPoint(BLOCK_SIZE*(i+1),(j+1)*BLOCK_SIZE),cvScalar(0,0,0),3);
            }
        }
    }
    cvShowImage(WINDOW_NAME,frame);
    cvWaitKey(2);
}

int Judge_Finish(CMap map)
{
    for(int i = 0;i < grey_block_num;i++)
    {
        if (map.block_step[i] != 2)
        {
            return 0;
        }
    }
    return 1;
}

void Draw_Patch(CMap map)
{
    Draw_frame_background();
    for(int i = 0;i < map.Patch_num-1;i++)
    {
        int x1 = map.patch[i].x;
        int y1 = map.patch[i].y;
        int x2 = map.patch[i+1].x;
        int y2 = map.patch[i+1].y;
        cvLine(frame,cvPoint(BLOCK_SIZE*x1+BLOCK_SIZE/2,BLOCK_SIZE*y1+BLOCK_SIZE/2),
                    cvPoint(BLOCK_SIZE*x2+BLOCK_SIZE/2,BLOCK_SIZE*y2+BLOCK_SIZE/2),cvScalar(0,0,255),3);
    }
    cvShowImage(WINDOW_NAME,frame);
    cvWaitKey(0);

}

void Figure_puzzle(CMap m_map,CPoint next)
{
    if(next.x < 0 || next.y < 0 || next.x >= N || next.y >= M)
        return;

    if (m_map.map[next.y][next.x] != 0)
        return;
    //cout< <next.x<<" "<<next.y<<endl;
    //Draw_Patch(m_map);

    m_map.map[next.y][next.x] = 1;
    if (g_map[next.y][next.x] != 0)
    {
        m_map.block_step[g_map[next.y][next.x]-1]++;
        if(m_map.block_step[g_map[next.y][next.x]-1] > 2)
            return;
    }
    m_map.patch[m_map.Patch_num] = next;
    m_map.Patch_num++;

    if (next.x == N-1 && next.y == 0)
    {
        if (Judge_Finish(m_map))
        {
            //输出结果
            for(int i = 0;i < m_map.Patch_num;i++)
            {
                cout<<"("<<m_map.patch[i].x<<","<<m_map.patch[i].y<<")->";
            }
            cout< <endl;
            Draw_Patch(m_map);
            //system("pause");
            return;
        }
    }

    Figure_puzzle(m_map,CPoint(next.x-1,next.y));
    Figure_puzzle(m_map,CPoint(next.x+1,next.y));
    Figure_puzzle(m_map,CPoint(next.x,next.y-1));
    Figure_puzzle(m_map,CPoint(next.x,next.y+1));
}

void InitMap(CMap &m_map)
{
    for(int i = 0;i < M;i++)
    {
        for(int j = 0;j < N;j++)
        {
            m_map.map[i][j] = 0;
            m_map.patch[7*i + j].x = -1;
            m_map.patch[7*i + j].y = -1;
        }
    }
    for(int i = 0;i < grey_block_num;i++)
    {
        m_map.block_step[i] = 0;
    }
    m_map.Patch_num = 0;
}

int main(int argc,char* argv[])
{
    CMap m_map;
    frame = cvCreateImage(cvSize(BLOCK_SIZE*N,BLOCK_SIZE*M),IPL_DEPTH_8U,3);
    cvNamedWindow(WINDOW_NAME);
    Draw_frame_background();
    InitMap(m_map);
    Figure_puzzle(m_map,CPoint(0,M-1));
    //system("pause");
    return 0;
}