usaco_5_2_3_wissqu.cpp

usaco自己做的1到5章的代码

/*
PROB: wissqu 
LANG: C++
*/
/*
这道题，暴力搜索就行了……貌似没什么优化啊，最大的优化就是usaco已经告诉你的，每次先从D开始放牛……
时间还给了5sec，而且本题做完后会发现……原来数据只有……还是……o(∩_∩)o...
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cmath>
#include<algorithm>
#include<iomanip>
//#define cin fin
using namespace std;
int map[6][6],num[5];
bool used[5][5];
struct MOVE{
	int cow,i,j;
};
int sum;
MOVE mov[16],tmov[16];
inline bool check(int i,int j,int tn)
{
	return map[i-1][j-1]!=tn && map[i-1][j]!=tn && map[i-1][j+1]!=tn
		&& map[i][j-1]!=tn && map[i][j]!=tn && map[i][j+1]!=tn
		&& map[i+1][j-1]!=tn && map[i+1][j]!=tn && map[i+1][j+1]!=tn;
}
void dfs(int dep,int tn)
{
	if(dep==16)
	{
		if(sum==0) memcpy(mov,tmov,sizeof(tmov));
		sum++;
		return;
	}
	int temp,tcow;
	tcow=tn;
	for(int i=1;i<5;i++)
		for(int j=1;j<5;j++){
			if(!used[i][j] && check(i,j,tn)){
				num[tn]--;
				used[i][j]=true;
				temp=map[i][j];
				map[i][j]=tn;
				tmov[dep].cow=tcow;
				tmov[dep].i=i;
				tmov[dep].j=j;
				if(dep==15) 
					dfs(dep+1,0);
				else 
				for(int k=0;k<5;k++)
					if(num[k])
						dfs(dep+1,k);
				map[i][j]=temp;
				num[tn]++;
				used[i][j]=false;				
			}
		}
}
int main()
{
	ifstream fin("wissqu.in");
	ofstream fout("wissqu.out");
    int i,j,k,des;
	char ch;
	memset(map,1000,sizeof(map));
	memset(num,0,sizeof(num));
	memset(used,false,sizeof(used));
	for(i=1;i<5;i++)
		for(j=1;j<5;j++)
		{
			fin>>ch;
			map[i][j]=ch-'A';
			num[map[i][j]]++;
		}
	num['D'-'A']++; num['C'-'A']--;
	dfs(0,'D'-'A');
	for(i=0;i<16;i++) fout<<(char)(mov[i].cow+'A')<<' '<<mov[i].i<<' '<<mov[i].j<<endl;
	fout<<sum<<endl;
    return 0;
}