C++ lianliankan judge graph elimination algorithm

  • 2020-06-23 01:19:37
  • OfStack

We played the lianlianzang game, by selecting the same elements of two graphics, determine whether it can be connected in three turns, if it can, then eliminate, if not, then can not eliminate, until finally all eliminate.

The algorithm does not include the decision of deadlock state.


//  lianliankan .cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream.h>
#include <vector>
#include <queue>
 
 
using namespace std;
 
struct Point
{
  int x;
  int y;
};
 
int pushonelinespot(Point a,Point b,int c[6][6], queue<Point> &g)  // will a A point that can be reached in a straight line is queued g In the 
{
  int i;
  Point temp;
  for(i=1;;i++)  // Downward detection 
   { if((a.x+i)<=5&&c[a.x+i][a.y]==0)
      { 
    temp.x=a.x+i;temp.y=a.y;  
     g.push(temp);}  
     else if(c[a.x+i][a.y]!=0&&(a.x+i)<=5)
      {if((a.x+i)==b.x&&a.y==b.y) return 1;
       else break;}
     else break;
    }
   for(i=-1;;i--)   // Up testing 
   { if(c[a.x+i][a.y]==0&&(a.x+i)>=0)
      { temp.x=a.x+i;temp.y=a.y;  
       g.push(temp);}
     else if(c[a.x+i][a.y]!=0&&(a.x+i)>=0)
      {if((a.x+i)==b.x&&a.y==b.y) return 1;
       else break;}
     else break;
    }
   for(i=1;;i++)   // To the right test 
   { if(c[a.x][a.y+i]==0&&(a.y+i)<=5)
      { temp.x=a.x;temp.y=a.y+i;  
       g.push(temp);}
     else if(c[a.x][a.y+i]!=0&&(a.y+i)<=5)
      {if(a.x==b.x&&(a.y+i)==b.y) return 1;
       else break;}
     else break;
    }
   for(i=-1;;i--)  // To detect 
   { if(c[a.x][a.y+i]==0&&(a.y+i)>=0)
      { temp.x=a.x;temp.y=a.y+i;  
       g.push(temp);}
     else if(c[a.x][a.y+i]!=0&&(a.y+i)>=0)
      {if(a.x==b.x&&(a.y+i)==b.y) return 1;
       else break;}
     else break;
    }
   return 0;
}
 
bool shortestline(Point a,Point b,int c[6][6])
{
  if(c[a.x][a.y]==c[b.x][b.y])
  {
  Point temp;
  queue<Point> X,Y,Z;
  int i;
  i=pushonelinespot(a,b,c,X);
  if(i==1) return 1;
  while(!X.empty())
   { temp=X.front();X.pop();
    i=pushonelinespot(temp,b,c,Y);
    if(i==1) return 1; }  // The first 1 Time to turn 
   while(!Y.empty())
    { temp=Y.front();Y.pop();
     i=pushonelinespot(temp,b,c,Z);
     if(i==1) return 1;}  // The first 2 Time to turn 
 cout<<" The turning path is greater than twice "<<endl;
   return 0;
  }
 else if(c[a.x][a.y]==0||c[b.x][b.y]==0) {cout<<" The figure is empty, please re-enter: "<<endl;}
  else { cout<<" The two figures are different "<<endl;return 0;}
}
 
int main()
{
  int v,i,j;
  int c[6][6]={{0,0,0,0,0,0},{0,1,3,3,4,0},{0,0,6,4,0,0},{0,4,0,2,1,0},{0,6,0,4,2,0},{0,0,0,0,0,0}};
/*  for(i=0;i<6;i++)
    {for(j=0;j<6;j++)
  c[i][j]=0;}            // Initialize the 2 Dimensional array 
  cout<<" Please initialize the array matrix: "<<endl;
  while(cin>>value)           // The input control 
    {
      for(i=0;i<6;i++)
       {for(j=0;j<6;j++)
         c[i][j]=value;}
    } // Initialize the 2 Dimensional array; //while*/ 
 for(i=0;i<6;i++)
    {
   for(j=0;j<6;j++)
   cout<<"    "<<c[i][j]<<"  ";cout<<endl;
  };
 Point a,b;
  
 
   for(i=0;;i++)
  {
  int sum=0;
  cout<<" Please enter coordinates: "<<endl;
    cin>>a.x>>a.y>>b.x>>b.y;
   if(a.x>0&&a.x<5&&a.y>0&&a.y<5&&b.x>0&&b.x<5&&b.y>0&&b.y<5)
   { 
 if(a.x==b.x&&a.y==b.y) {cout<<" Do not enter the same coordinates , Please re-enter: "<<endl;continue;}
 v=shortestline(a,b,c);
    if(v==1)
 {
  c[a.x][a.y]=0;c[b.x][b.y]=0;
         cout<<" Success to eliminate "<<endl;
 } 
  }
    else cout<<" The coordinate input is wrong, please input again :"<<endl; 
  for(i=0;i<6;i++)
    {
   for(j=0;j<6;j++)
       sum+=c[i][j];
  };
  if(sum==0) break;
   for(i=0;i<6;i++)
    {
   for(j=0;j<6;j++)
   cout<<"    "<<c[i][j]<<"  ";cout<<endl;
  };
 };
 cout<<" Congratulations on passing. "<<endl;
 getchar();
 return 0;
}

Related articles: