摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS搜出組合(在途中可以剪枝)

皇后解92個  , 也可以直接暴力

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
int used[10]={0},xy[10][2];/*xy[][0]->x xy[][1]->y*/
int check(int x,int y)
{
   int a;
   for(a=1;a<x;a++)
      if(abs(xy[a][0]-x)==abs(xy[a][1]-y))
        return 0;
   return 1;
}
int time=0,max,map[9][9];
void DFS(int now)/*now->x used->y*/
{
   int a,b,c;
   if(now==9)
     {
       time++;
       /*printf("--------------------\n");
       for(a=1;a<=8;a++)
          printf("%d %d\n",xy[a][0],xy[a][1]);*/
       int sum=0;
       for(a=1;a<=8;a++)
          sum+=map[xy[a][0]][xy[a][1]];
       if(sum>max) max=sum;
       return;
     }
   for(a=1;a<=8;a++) /*a->y*/
      if(used[a]==0&&check(now,a)==1)
        {
          xy[now][0]=now;
          xy[now][1]=a;
          used[a]=1;
          DFS (now+1);
          used[a]=0;
        }
}
main()
{
   int t;
   scanf("%d",&t);
   while(t--)
      {
         int a,b,c;
         for(a=1;a<=8;a++)
            for(b=1;b<=8;b++)
               scanf("%d",&map[a][b]);
         max=0;
         DFS(1);
         printf("%5d\n",max);
      }
   return 0;
/*  system("pause");*/
}