最大连线.cpp

海明码 出站入站序列 非递归生成树 九格填质数 七子控棋盘等等算法

#include<stdio.h>
const a[10][10]={
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,1,1,0,0,0,0,1,0},
 {0,1,1,0,0,1,1,1,1,0},
 {0,0,1,0,1,1,0,1,1,0},
 {0,0,0,0,0,1,1,1,1,0},
 {0,0,1,0,0,0,0,0,1,0},
 {0,1,1,1,1,0,0,0,1,0},
 {0,1,1,1,1,0,0,0,1,0},
 {0,0,0,0,1,1,1,1,1,0},
 {0,0,0,0,0,0,0,0,0,0},
 };
const v[4]={0,1,0,-1};
const h[4]={1,0,-1,0};
short f[10][10]={0};
short mark[10][10]={0};
struct point{
      int x,y;
     
}way[64]={0}，best_xy[64];;
int best;



  void search(int ii,int jj,int current)
  { int i,j,k,p;
		  way[current].x=ii;
		  way[current].y=jj;
		  mark[ii][jj]=1;
		  for(k=0;k<=3;k++)
		   {  i=ii+v[k];
		      j=jj+h[k];
		      if(a[i][j]==1 && mark[i][j]==0)
			{
			     search(i,j,current+1);
			     mark[i][j]=0;
			  }
		   }
		 if (current>best)
		 {	 for (k=1;k<=current;k++)
		   {  best_xy[k].x=way[k].x;
		      best_xy[k].y=way[k].y;
		       }
		best=current;
		}

   }
main()
{
  int g,n,p,m;
  best=0;
  for (g=1;g<=8;g++)
   for(p=1;p<=8;p++)
    if(a[g][p]==1)
    {way[1].x=g;
     way[1].y=p;
     mark[g][p]=0;
     search(g,p,1);
    }
  printf("\n");
  for(g=1;g<=8;g++,printf("\n"))
   for(p=1;p<9;p++) printf("%d",a[g][p]);

  for(n=1;n<best;n++){
  printf("(%d,%d)-->",best_xy[n].x,best_xy[n].y);
  if (n%10==0)printf("\n");}
  printf("(%d,%d)",best_xy[best].x,best_xy[best].y);

}