20160419 ADV

Two base station.
在给定的网格上有两个敌对的联盟，alpha联盟和beta联盟
alpha联盟的成员用1表示，beta联盟的成员用2表示，0表示空地。
现在要在空地建两个基站使其能覆盖所有alpha联盟的成员，但是不能覆盖beta联盟的成员
基站的覆盖半径为正整数，且至少有一个alpha成员由两个基站同时覆盖。
现在要求满足要求的两个最近的基站的距离，如果不满足输出-1

思路：
1. 定义一个4维数组d[9][9][9][9], 将任意两点的距离d[x][y][a][b], (x,y)到(a,b)存储起来。
2. 定义链表0，链表元素为下面的结构，存储所有的空地的座标和最大半径（不至于覆盖到beta联盟成员），目前最大半径还没有赋值。

typedef struct _node{
   int x,y,count,maxr;
}node;

2. 定义链表A，存储所有alpha联盟的节点座标
3. 定义链表B，存储所有beta联盟的节点座标
4. for 所有链表0的元素
        for 所有链表B的元素
               分别计算0的某一点和所有B中节点的距离，取最小的存入链表0的成员maxr
5. for 所有链表0的元素
        for 所有链表0的元素
             选取两个不同的点，每个alpha节点有个计数count，初始为0. i点遍历一遍，在覆盖内 count++， j点遍历一遍，在覆盖内count++。 然后再扫一遍链表A如果所有alpha节点count>0 且 至少一个节点count大于1，则满族条件。然后对这样的两点计算距离平方和，取个最小值。

// 20170419adv.cpp : 建设基站
#include <stdio.h>
#include <stdlib.h>

typedef struct _node0{
   int x,y,maxr;
   struct _node0 *nt;
}node0;

typedef struct _node1{
   int x,y,count;
   struct _node1 *nt;
}node1;

typedef struct _node2{
   int x,y;
   struct _node2 *nt;
}node2;

node0 *h0,*p0,*q0,*r0,*s0;
node1 *h1,*p1,*q1,*r1;
node2 *h2,*p2,*q2,*r2;
int nbr0,nbr1,nbr2;

int N;
int a[9][9];
int d[9][9][9][9];
int flag1,flag2,result,tmpmin;

void calc_distance(void)
{
   int i,j,k,l;
   for(i=0;i<9;i++)
      for(j=0;j<9;j++)
         for(k=0;k<9;k++)
            for(l=0;l<9;l++)
               d[i][j][k][l]=(i-k)*(i-k) + (j-l)*(j-l);
}

void linklist_initialize(void)
{
   int i,j;
   for(i=0;i<=N;i++)
   {
      for(j=0;j<=N;j++)
      {
         scanf("%d", &a[i][j]);
         if(a[i][j]==0)
         {
            p0=(node0*)malloc(sizeof(node0));
            p0->x=i;
            p0->y=j;
            p0->maxr=-1;
            p0->nt=NULL;
            if(h0==NULL)
               h0=p0;
            else
               q0->nt=p0;
            q0=p0;
            nbr0++;
         }
         else if(a[i][j]==1)
         {
            p1=(node1*)malloc(sizeof(node1));
            p1->x=i;
            p1->y=j;
            p1->count=0;
            p1->nt=NULL;
            if(h1==NULL)
               h1=p1;
            else
               q1->nt=p1;
            q1=p1;
            nbr1++;
         }
         else if(a[i][j]==2)
         {
            p2=(node2*)malloc(sizeof(node2));
            p2->x=i;
            p2->y=j;
            p2->nt=NULL;
            if(h2==NULL)
               h2=p2;
            else
               q2->nt=p2;
            q2=p2;
            nbr2++;
         }
         else{
            printf("Unexpected error\n");
         }
      }
   }
}

void calc_max_radius(void)
{
   int mr,tmp;
   int outflag=0;
   r0=h0;
   while(r0!=NULL)
   {
      mr=8;
      r2=h2;
      while(r2!=NULL)
      {
         tmp=d[r0->x][r0->y][r2->x][r2->y];
         if(tmp==1)
         {
            if(r0==h0)
            {
               h0=h0->nt;
               q0=h0;
               free(r0);
               r0=q0;
            }
            else
            {
               q0->nt=r0->nt;
               free(r0);
               r0=q0->nt;
            }
            nbr0--;
            outflag=1;
            break;
         }
         while(mr*mr >= tmp)
            mr--;
         r2=r2->nt;
      }
      if(outflag==1)
      {
         outflag=0;
         continue;
      }
      r0->maxr=mr;
      q0=r0;
      r0=r0->nt;
   }
}
void linklist_free(void)
{
   r0=h0->nt;
   while(r0!=NULL)
   {
      free(h0);
      h0=r0;
      r0=r0->nt;
   }
   free(h0);
   h0=p0=q0=r0=s0=NULL;

   r1=h1->nt;
   while(r1!=NULL)
   {
      free(h1);
      h1=r1;
      r1=r1->nt;
   }
   free(h1);
   h1=p1=q1=r1=NULL;

   r2=h2->nt;
   while(r2!=NULL)
   {
      free(h2);
      h2=r2;
      r2=r2->nt;
   }
   h2=p2=q2=r2=NULL;
}

int main(int argc, char* argv[])
{
   int t,test_case;

   calc_distance();

   freopen("20170419in.txt","r",stdin);
   scanf("%d", &test_case);
   for(t=1;t<=test_case;t++)
   {
      scanf("%d",&N);
      h0=NULL;
      h1=NULL;
      h2=NULL;
      nbr0=nbr1=nbr2=0;

      linklist_initialize();

      calc_max_radius();//calc max radius for every point in 0 linklist

      result=-1;
      tmpmin=0;
      r0=h0;
      while(r0!=NULL)
      {
         s0=r0->nt;
         while(s0!=NULL)
         {
            flag1=1;
            flag2=0;
            r1=h1;//For any two-point combination, all alpha's counter must be initialized
            while(r1!=NULL)
            {
               r1->count=0;
               r1=r1->nt;
            }

            r1=h1;
            while(r1!=NULL)
            {
               if((r0->maxr)*(r0->maxr) >= d[r0->x][r0->y][r1->x][r1->y])
                  r1->count++;
               r1=r1->nt;
            }
            r1=h1;
            while(r1!=NULL)
            {
               if((s0->maxr)*(s0->maxr) >= d[s0->x][s0->y][r1->x][r1->y])
                  r1->count++;
               r1=r1->nt;
            }
            r1=h1;
            while(r1!=NULL)
            {
               if(r1->count<1)
               {
                  flag1=0;
                  break;
               }
               if(r1->count>1)
                  flag2=1;
               r1=r1->nt;
            }
            if(flag1==1 && flag2==1)
            {
               tmpmin=d[r0->x][r0->y][s0->x][s0->y];
               if(result==-1)
                  result=tmpmin;
               else if(result>tmpmin)
                  result=tmpmin;
            }

            s0=s0->nt;
         }//inner while
         r0=r0->nt;
      }//outer while

      printf("#%d %d\n",t,result);

      linklist_free();
   }//every cases

   fclose(stdin);
   return 0;
}

/* input
5
5
0 2 0 2 0 2
2 0 2 0 1 0
0 2 0 1 0 1
2 0 1 0 1 0
0 2 0 1 0 2
2 0 2 0 2 0
7
0 0 0 0 0 2 0 0
0 0 0 1 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
0 2 0 0 0 0 0 1
2 0 0 0 0 0 0 0
0 0 2 0 1 0 0 0
7
0 0 0 0 0 2 0 0
0 0 0 1 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0
0 0 1 0 0 0 0 0
0 2 0 0 0 0 0 1
2 0 0 0 0 0 0 0
0 0 2 0 1 0 0 0
8
2 0 0 0 0 0 0 2 0
0 2 0 0 0 0 0 0 2
0 0 2 0 0 0 0 0 2
2 0 0 1 1 2 2 0 0
0 0 1 0 0 1 2 2 0
1 0 0 1 0 0 0 0 0
0 1 0 1 0 0 1 0 0
0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 2
8
2 0 0 0 0 0 2 0 0
1 0 0 0 0 0 0 2 2
1 0 0 0 1 2 0 0 2
0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 2 0
0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0
2 0 0 0 2 0 2 2 0
*/

/*
#1 2
#2 8
#3 -1
#4 5
#5 4
*/