// MyLinkup.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

//grid's intial size

const int nSize = 8;

struct Point{

int x;

int y;

Point(){

this->x = INT_MAX;

this->y = INT_MAX;

}

bool operator==(Point x){

return this->x==x.x && this->y==x.y;

}

};

//grid point

struct GridPoint{

Point c;

int Len;

int Cross;

//Cross is definitely ascending order, how about Len?

//Dijkstra algorithm

GridPoint(){

this->Len = INT_MAX;

this->Cross = INT_MAX;

}

int operator<(GridPoint item){

if(this->Cross < item.Cross)

return true;

if(this->Cross > item.Cross)

return false;

//==

return this->Len < item.Len;

}

int operator>(GridPoint item){

if(this->Cross > item.Cross)

return true;

if(this->Cross < item.Cross)

return false;

//==

return this->Len > item.Len;

}

};

//ms solution, keep to backtrack

struct MinPoint{

int MinCross;

double MinLen;

MinPoint(){

this->MinCross = INT_MAX;

this->MinLen = DBL_MAX;

}

};

//implementation

int** Intial(int** grid, const int type, const int count, vector<Point>& _pre);

void Linkup(int** grid, vector<Point>& _pre, const int type, const int count);

bool FindPath(int** grid, const int type, const int count, Point start, Point end);

void PrintOut(int** grid);

double dis(int x, int y, int x1, int y1){

return abs( x - x1 ) + abs( y - y1 );

}

int** Intial(int** grid, const int type, const int count, vector<Point>& _pre){

int* v = new int[type]();

for(int i = 0; i < type; i++)

v = count;

//rand() for select abitrary type

srand((unsigned)time(0));

int RANGE_MIN = 0, RANGE_MAX = type;//end can't reach

int POINT_MIN = 0, POINT_MAX = nSize;

for(int total = count * type; total > 0; ){

//select the type

int ctype = 0;

for(ctype = ( (double)rand() / (double)RAND_MAX ) * RANGE_MAX + RANGE_MIN;;){

if(v[ctype] != 0)

break;

else{

ctype = ( (double)rand() / (double)RAND_MAX ) * RANGE_MAX + RANGE_MIN;

}

}

//for[j]

Point n;

n.x = ( (double)rand() / (double)RAND_MAX ) * POINT_MAX + POINT_MIN;

n.y = ( (double)rand() / (double)RAND_MAX ) * POINT_MAX + POINT_MIN;

if(find(_pre.begin(), _pre.end(), n)==_pre.end()){

//can't find

grid[n.x][n.y] = ctype + 1;

v[ctype]--;

total--;

_pre.push_back(n);

}

}

return grid;

}

void Linkup(int** grid, vector<Point>& _pre, const int type, const int count){

while(_pre.size() > 0){

//enter the logic

int pair = 0, x = 0, y = 0;

Point start, end;

cout<<endl;

while((pair += scanf("%d,%d", &x, &y)) <= 4){

fflush(stdin);

if(x>-1&&x<nSize&&y>-1&&y<nSize&&grid[x][y]){

if(pair==2){

start.x = x;

start.y = y;

}

else{

if(start.x != x || start.y != y){

end.x = x;

end.y = y;

break;

}

else{

pair -= 2;

cout<<" start mustn't be equal with end"<<endl;

}

}

}

else{

pair -= 2;

cout<<" invalid"<<endl;

}

}

//get valid start and end position

if(grid[start.x][start.y] == grid[end.x][end.y]){

//check if find the found or not

if(FindPath(grid, type, count, start, end)){

//erase i and j

vector<Point>::iterator i = find(_pre.begin(), _pre.end(), start);

if(i!=_pre.end())

_pre.erase(i);

vector<Point>::iterator j = find(_pre.begin(), _pre.end(), end);

if(j!=_pre.end())

_pre.erase(j);

//erase the current point

grid[start.x][start.y] = 0;

grid[end.x][end.y] = 0;

PrintOut(grid);

}

else

cout<<" no path to reach"<<endl;

}

else

cout<<" not equal"<<endl;

}

}

bool FindPath(int** grid, const int type, const int count, Point start, Point end){

//offset

Point offset[4];

offset[0].x = -1; offset[0].y = 0; //left

offset[1].x = 1; offset[1].y = 0; //right;

offset[2].x = 0; offset[2].y = -1; //up

offset[3].x = 0; offset[3].y = 1;//down

int NumofNbrs = 4;

//step information structure

GridPoint here, nbr;

here.Len = 0;

here.c = start;

here.Cross = -1;

//backtrack array

MinPoint** track = new MinPoint*[nSize]();

for(int i = 0; i < nSize; i++)

track = new MinPoint[nSize]();

track[start.x][start.y].MinCross = -1;

track[start.x][start.y].MinLen = 0;

//previous step information

Point** pre = new Point*[nSize]();

for(int i = 0; i < nSize; i++)

pre = new Point[nSize]();

pre[start.x][start.y].x = -1;

pre[start.x][start.y].y = -1;

//if we have step the grid or not?

bool** step = new bool*[nSize]();

for(int i = 0; i < nSize; i++)

step = new bool[nSize]();

MinHeap<GridPoint> Q;

Q.Insert(here);

while(Q.size() > 0){

here = Q.DeleteMin();

//judge path

for(int i = 0 ; i < NumofNbrs; i++){

//offset

int x = here.c.x + offset.x;

int y = here.c.y + offset.y;

for(;x>-1&&x<nSize&&y>-1&&y<nSize; x += offset.x, y += offset.y){

nbr.c.x = x;

nbr.c.y = y;

if(track[x][y].MinCross > track[here.c.x][here.c.y].MinCross + 1 ||

( track[x][y].MinCross == track[here.c.x][here.c.y].MinCross + 1

&& track[x][y].MinLen > track[here.c.x][here.c.y].MinLen + dis(x, y, here.c.x, here.c.y) ) ){

//update information

track[x][y].MinCross = track[here.c.x][here.c.y].MinCross + 1;

if(track[x][y].MinLen > track[here.c.x][here.c.y].MinLen + dis(x, y, here.c.x, here.c.y))

track[x][y].MinLen = track[here.c.x][here.c.y].MinLen + dis(x, y, here.c.x, here.c.y);

pre[x][y].x = here.c.x;

pre[x][y].y = here.c.y;

}

if(grid[x][y]!=0){

//first non-space, break;

break;

}

else{

if(!step[x][y]){

//set the priority information

nbr.Cross = track[x][y].MinCross;

nbr.Len = track[x][y].MinLen;

//set step information

step[x][y] = true;

Q.Insert(nbr);

}

}

}

if(nbr.c == end)

break;

}//for

if(nbr.c == end)

break;

}

cout<<nbr.c.x<<","<<nbr.c.y<<" "<<nbr.Len<<"[Len] "<<nbr.Cross<<"[Cross] "<<endl;

if(nbr.c.x == end.x && nbr.c.y == end.y && nbr.Cross <= 3){

//print path

cout<<" Path : ";

for(int x = nbr.c.x, y = nbr.c.y; x != -1 && y != -1;){

cout<<"("<<x<<","<<y<<")";

int px = pre[x][y].x;

int py = pre[x][y].y;

x = px;

y = py;

if(x!=-1&&y!=-1)

cout<<" <- ";

else break;

}

cout<<endl;

return true;

}

return false;

}

void PrintOut(int** grid){

for(int i = 0; i < nSize; i++){

for(int j = 0; j < nSize; j++){

if(grid[j]==0)

cout<<" ";

else cout<<grid[j]<<" ";

}

cout<<"| x = "<<i<<endl;

}

}

int _tmain(int argc, _TCHAR* argv[])

{

//initialization for grid

int** grid = new int*[nSize]();

for(int i = 0; i < nSize; i++)

grid = new int[nSize]();

vector<Point> _pre;

//call intial

grid = Intial(grid, 5, 4, _pre);

PrintOut(grid);

Linkup(grid, _pre, 5, 4);

QUIT();

return 0;

}