首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >故人的一份连连看代码,c语言版本

故人的一份连连看代码,c语言版本

作者头像
Jerry Wang
发布2019-05-31 15:57:09
5070
发布2019-05-31 15:57:09
举报

版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1440103

花一天时间写的一个连连看,唉!分支限界有的关键点,还是不是掌握的很清楚,居然搞那么长时间,应该 
在3个小时之内轻松拿下的,加油了 
// 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;
} 
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年12月01日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档