记录编号	81531	评测结果	A
题目名称	威斯康星州的牧场	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.933 s
提交时间	2013-11-15 17:19:00	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=7;
char board[SIZEN][SIZEN]={0};
int dx[9]={0,0,0,1,1,1,-1,-1,-1};
int dy[9]={0,1,-1,1,0,-1,1,0,-1};
int calf[SIZEN]={0};
int sum=0;
class OPT{
public:
	char tp;
	int x,y;
};
deque<OPT> ans;
inline int mabs(int x){
	return x>=0?x:-x;
}
bool check_legal(int x,int y,char ch){
	int i;
	int temp;
	for(i=0;i<=8;i++){
		temp=mabs((int)ch-(int)board[x+dx[i]][y+dy[i]]);
		if(temp==0||temp==32){
			//cout<<ch<<board[x+dx[i]][y+dy[i]];
			return false;
		}
	}
	return true;
}
bool DFS(int leftnum){
	if(leftnum==0){
		if(sum==0){
			sum++;
			return true;
		}
		sum++;
		return false;
	}
	int i,x,y;
	char ch;
	bool flag=false;
	int temp;
	if(leftnum==16){
		i=3;
		calf[i]--;
		for(x=1;x<=4;x++){
			for(y=1;y<=4;y++){
				if(board[x][y]>='a') continue;
				if(!check_legal(x,y,i+'a')) continue;
				ch=board[x][y];
				board[x][y]=i+'a';
				//cout<<x<<" "<<y<<endl;
				if(DFS(leftnum-1)){
					ans.push_front((OPT){char(i+'A'),x,y});
					flag=true;
				}
				board[x][y]=ch;
			}
		}
		calf[i]++;
		return flag;
	}
	for(i=0;i<=4;i++){
		if(!calf[i]) continue;
		calf[i]--;
		for(x=1;x<=4;x++){
			for(y=1;y<=4;y++){
				if(board[x][y]>='a') continue;
				if(!check_legal(x,y,i+'a')) continue;
				ch=board[x][y];
				board[x][y]=i+'a';
				//cout<<"("<<x<<","<<y<<")";
				if(DFS(leftnum-1)){
					ans.push_front((OPT){char(i+'A'),x,y});
					flag=true;
				}
				board[x][y]=ch;
			}
		}
		calf[i]++;
	}
	return flag;
}
void init(void){
	int i,j;
	for(i=1;i<=4;i++){
		for(j=1;j<=4;j++){
			cin>>board[i][j];
		}
		getchar();
	}
	calf[0]=3,calf[1]=3,calf[2]=3,calf[3]=4,calf[4]=3;
}
void printanswer(void){
	int i;
	for(i=0;i<ans.size();i++) printf("%c %d %d\n",ans[i].tp,ans[i].x,ans[i].y);
}
int main(){
	freopen("wissqu.in","r",stdin);
	freopen("wissqu.out","w",stdout);
	init();
	DFS(16);
	printanswer();
	printf("%d\n",sum);
	return 0;
}