暴力搜索, 加上限制条件.
能过样例就可以了.
/**//*
ID: lorelei3
TASK: wissqu
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
struct Move
{
int ch,c,r;
};
ifstream fin("wissqu.in");
ofstream fout("wissqu.out");
int map[6][6], cnt[6], tot;
bool used[6][6];
Move ans[20],tmp[20];
void input(){
char ch;
for(int i=1; i<=4; ++i){
for(int j=1; j<=4; ++j){
fin>>ch;
map[i][j]=ch-'A'+1;
cnt[map[i][j]]++;
}
fin.get();
}
cnt[3]--;
cnt[4]++;
}
void dfs(int d, int ch){
if(d>=16){
if(tot==0)
memcpy(ans, tmp, sizeof(ans));
tot++;
return;
}
for(int i=1; i<=4; ++i)
for(int j=1; j<=4; ++j)
if(!used[i][j] && map[i+1][j+1]!=ch && map[i+1][j]!=ch && map[i+1][j-1]!=ch &&
map[i][j+1]!=ch && map[i][j]!=ch &&map[i][j-1]!=ch &&
map[i-1][j+1]!=ch && map[i-1][j]!=ch && map[i-1][j-1]!=ch){
int t = map[i][j];
map[i][j]=ch;
cnt[ch]--;
used[i][j]=true;
tmp[d].ch = ch;
tmp[d].r = i;
tmp[d].c = j;
if(d==15)
dfs(d+1, 0);
else{
for(int k=1; k<=5; ++k)
if(cnt[k])
dfs(d+1, k);
}
map[i][j]=t;
cnt[ch]++;
used[i][j]=false;
}
}
void output(){
for(int i=0; i<16; ++i)
fout<<(char)(ans[i].ch-1+'A')<<" "<<ans[i].r<<" "<<ans[i].c<<endl;
fout<<tot<<endl;
}
int main(){
input();
dfs(0, 4);
output();
return 0;
}posted on 2011-02-10 11:11
小阮 阅读(272)
评论(0) 编辑 收藏 引用 所属分类:
USACO