连连看

#include <vector>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;
enum direction{
    north = 0,
    east,
    south,
    west,
    center,
    error
};

typedef struct  pointInfo
{
    int x;
    int y;
} Point;

typedef vector<Point> pVector;
typedef vector<Point>::iterator pIter;

typedef struct routeInfo
{
    //enum direction pre_direction;    
    pVector point_vector;
} Route;




int map[6][6] = {
    {0,0,0,0,0,0},
    {0,1,0,0,0,0},
    {0,1,0,1,0,0},
    {0,1,0,1,0,0},
    {0,0,0,0,0,0},
    {0,0,0,0,0,0}
                };

enum direction getDirection2(Point* p1, Point* p2)
{
    if (p1->x -p2->x == 1 && p1->y - p2->y == 0)
        return west;
    else if (p1->x - p2->x == -1 && p1->y - p2->y == 0)
        return east;
    else if (p1->x - p2->x == 0 && p1->y - p2->y == 1)
        return north;
    else if (p1->x - p2->x == 0 && p1->y - p2->y == -1)
        return south;
    else {
        //error
        return error;
    }
};

enum direction getDirection(Route* r)
{
    if (r->point_vector.size() <2)
    {
        return center;
    }else
    {
        return getDirection2(&r->point_vector[r->point_vector.size()-2], &r->point_vector[r->point_vector.size()-1]);
    }
}



int getCurTurns(Route* t)
{
    int turns = 0;
    if (t->point_vector.size() >2)
    {
        enum direction preDirection = center;
        enum direction curDirection;
        for (int i = 0; i < t->point_vector.size() - 1; i++)
        {
            curDirection = getDirection2(&t->point_vector[i], &t->point_vector[i+1]);
            if (preDirection != center && preDirection != curDirection)
            {
                turns ++;
            }
            preDirection = curDirection;
        }
    }   
    return turns;
};

//only turn num < 2 can be the neighbors
void setNeighbors(Route* r, Point* p, pVector* neighbors)
{
    r->point_vector.push_back(*p);
    if (getCurTurns(r) < 3)
        neighbors->push_back(*p);
    r->point_vector.pop_back();
}


pVector getMovableNeighbors(Point* p, Point* end, Route* r)
{
    pVector neighbors;
    enum direction direct;
    direct = getDirection(r);


    //east
    if (p->x + 1 < 6 //border
        && map[p->y][p->x + 1] != 1//movable
        && direct != west // can not go back
        )
    {
        Point n;
        n.x = p->x + 1; n.y = p->y;
        setNeighbors(r, &n, &neighbors);
    }
    //west
    if (p->x - 1 >= 0  //border
        && map[p->y][p->x - 1] != 1 //movable
        && direct != east // can not go back
        )
    {
        Point n;
        n.x = p->x - 1; n.y = p->y;
        setNeighbors(r,&n, &neighbors);
    }
    //south
    if (p->y + 1 < 6  //border
        && map[p->y + 1][p->x] != 1 //movable
        && direct != north // can not go back       
        )
    {
        Point n;
        n.x = p->x; n.y = p->y + 1;
        setNeighbors(r,&n, &neighbors);
    }
    //north
    if (p->y - 1 >= 0  //border
        && map[p->y - 1][p->x] != 1 //movable
        && direct != south // can not go back           
        )
    {
        Point n;
        n.x = p->x ; n.y = p->y - 1;
        setNeighbors(r,&n, &neighbors);
    }
    return neighbors;
}

void printTheRoute(Route* aRoute)
{
    ostringstream ost;
    ost << "The Route is : turn " << getCurTurns(aRoute)<< "\n";
   
    for(int i = 0 ; i < aRoute->point_vector.size(); i++)
    {
        ost << "[" << aRoute->point_vector[i].x << "," << aRoute->point_vector[i].y << "]";
        if (i != aRoute->point_vector.size() - 1)
        {
            ost << " -> ";
        }
       
    }
    cout << ost.str() << "\n";
}


void move_step(Point* start, Point* end, Route* r)
{
    //get point's neighbor
    //if the neighbor is the target, mission end
    //else move_step(neighbor)
            pVector neighbors = getMovableNeighbors(start, end, r);
            pIter it;
            for (it = neighbors.begin(); it != neighbors.end(); it++)
            {
                if (it->x == end->x && it->y == end->y)
                {
                    //Found!!
                    r->point_vector.push_back(*end);
                    printTheRoute(r);
                    r->point_vector.pop_back();
                }else
                {
                    r->point_vector.push_back(*it);   
                    //printTheRoute(r);
                    move_step(it, end, r);
                    r->point_vector.pop_back();
                    //printTheRoute(r);
                }

            }
}




void test();

void main()
{
    //cout << "hello world!\n";
    //test();
    Route aRoute;
   
    Point start;
    Point des;
    start.x = 1; start.y = 1;
    des.x = 3; des.y = 3;
     aRoute.point_vector.push_back(start);

    map[des.y][des.x] = 0;
    move_step(&start, &des, &aRoute);

}

void test()
{
    Point p1;
    p1.x = 10;
    p1.y = 5;

    Point p2;
    p2.x = 10; p2.y = 6;

    pVector points;
    points.push_back(p1);
    points.push_back(p2);

    Route aRoute;
    aRoute.point_vector = points;

    for(int i = 0 ; i < aRoute.point_vector.size(); i++)
    {
        ostringstream ost;
        ost << "point x: " << aRoute.point_vector[i].x << " point y: " << aRoute.point_vector[i].y << "\n";
        cout << ost.str();
    }

}