这题真搞~就一组数据....囧~~~
按他的要求枚举搜索就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;
}