USACO Section 5.2 Wisconsin Squares - 按要求DFS就行了..

这题真搞~就一组数据....囧~~~

按他的要求枚举搜索就ok了..当然要输出字典序最小的解~~~那就按字典序来搜索..除了最开始是确定D..后面的都是先确定较小的A,B,C,D,E..再确定较小的Y..再确定较小的X...如此搜出的第一个解就是字典序最小的答案...

开始还想着Hash...结果写完了样例过了...一交就A了...似乎这题不需要Hash..

Program:

/*  
ID: zzyzzy12   
LANG: C++   
TASK: wissqu
*/      
#include<iostream>      
#include<istream>  
#include<stdio.h>     
#include<string.h>      
#include<math.h>      
#include<stack>
#include<map>
#include<algorithm>      
#include<queue>   
#define oo 2000000005  
#define ll long long  
#define pi (atan(2)+atan(0.5))*2 
using namespace std;
char s[6][6];
bool used[6][6];
int num,have[5];
struct node
{
      char t;
      int y,x;     
}way[20];
bool ok(int y,int x,char c)
{
      if (used[y][x] || s[y][x]==c) return false;
      if (s[y][x+1]==c || s[y][x-1]==c || s[y+1][x]==c || s[y-1][x]==c) return false;
      if (s[y+1][x+1]==c || s[y+1][x-1]==c ) return false;
      if (s[y-1][x+1]==c || s[y-1][x-1]==c) return false;
      return true;       
} 
void DFS(int step)
{
      int x,y,i;
      char c;
      if (step==17)
      {
             if (!num)
             {
                    for (i=1;i<=16;i++)
                        printf("%c %d %d\n",way[i].t,way[i].y,way[i].x);  
             }      
             num++;
             return;       
      }
      for (i=0;i<5;i++)
        if (have[i])
        {
               have[i]--;
               for (y=1;y<=4;y++)
                 for (x=1;x<=4;x++)
                 if (ok(y,x,'A'+i))
                 {
                        used[y][x]=true;  c=s[y][x];
                        s[y][x]='A'+i;  
                        way[step].t=i+'A'; way[step].y=y; way[step].x=x;
                        DFS(step+1);      
                        s[y][x]=c;        used[y][x]=false;  
                 }
               have[i]++;
        }     
      return;       
}
int main()  
{  
      freopen("wissqu.in","r",stdin);   
      freopen("wissqu.out","w",stdout);
      int i,j;
      char c;
      for (i=0;i<=5;i++) s[0][i]=s[i][0]=s[5][i]=s[i][5]='?';
      for (i=1;i<=4;i++) scanf("%s",s[i]+1);
      num=0;
      memset(used,false,sizeof(used));
      have[0]=have[1]=have[2]=have[4]=3; have[3]=4;
      for (i=1;i<=4;i++)
         for (j=1;j<=4;j++)
            if (ok(i,j,'D'))
            {
                  c=s[i][j];   s[i][j]='D';
                  used[i][j]=true;  have[3]--;
                  way[1].t='D'; way[1].y=i; way[1].x=j;
                  DFS(2);  have[3]++;  
                  s[i][j]=c;    used[i][j]=false; 
            }
      printf("%d\n",num);
      return 0;     
}