USACO 3.2.5 Magic Squares (康托hash + BFS) - 小阮的菜田 - C++博客

随笔-141 评论-9 文章-3 trackbacks-0

USACO 3.2.5 Magic Squares (康托hash + BFS)

康托hash + BFS

/*

ID: lorelei3

TASK: msquare

LANG: C++

*/

#include <fstream>

#include <memory.h>

#include <algorithm>

#include <functional>

#include <queue>

using namespace std;

const int MAX = 40330;

typedef struct {

int hash;

int str[10];

char op;

int pre;

int index;

}Node;

Node nodes[MAX];

bool used[MAX];

int fac[10];

int dest[10];

int target,cnt;

char ops[MAX];

int cantor_hash(int a[]){

int ans=0;

bool in[10];

memset(in, false, 10);

for(int i=0; i<8; ++i){

int k=a[i];

in[k]=true;

int tmp =k;

for(int j=1; j<k; ++j)

if(in[j])

--tmp;

--tmp;

ans+=fac[7-i]*tmp;

}

return ans+1;

}

void init(){

memset(used, false, sizeof(used));

for(int i=0; i<8; ++i)

nodes[cnt].str[i] = i+1;

int k;

fac[0]=fac[1]=1;

for(k=2; k<10; ++k)

fac[k] = k*fac[k-1];

}

void change(int a[]){

for(int i=0; i<4; ++i){

int tmp = a[i];

a[i] = a[7-i];

a[7-i] = tmp;

}

}

void insert(int a[]){

int i,tmp;

tmp = a[3];

for(i=2; i>=0; --i)

a[i+1] = a[i];

a[0] = tmp;

tmp = a[4];

for(i=5; i<8; ++i)

a[i-1] = a[i];

a[7] = tmp;

}

void rotate(int a[]){

int tmp;

tmp=a[1];

a[1]=a[6];

a[6]=tmp;

tmp=a[2];

a[2]=a[5];

a[5]=tmp;

tmp=a[2];

a[2]=a[6];

a[6]=tmp;

}

void bfs(){

int v, top;

Node tmp;

queue<int> Q;

cnt=0;

nodes[cnt].hash = cantor_hash(nodes[cnt].str);

nodes[cnt].index = 0;

nodes[cnt].pre = -1;

used[nodes[cnt].hash] = true;

Q.push(cnt);

while(!Q.empty()){

top = Q.front();

Q.pop();

tmp = nodes[top];

change(tmp.str);

v = cantor_hash(tmp.str);

if(!used[v]){

cnt++;

used[v] = true;

tmp.op = 'A';

tmp.hash = v;

tmp.pre = nodes[top].index;

tmp.index = cnt;

nodes[cnt] = tmp;

Q.push(cnt);

}

if(v==target)

break;

tmp = nodes[top];

insert(tmp.str);

v = cantor_hash(tmp.str);

if(!used[v]){

cnt++;

used[v] = true;

tmp.op = 'B';

tmp.hash = v;

tmp.pre = nodes[top].index;

tmp.index = cnt;

nodes[cnt] = tmp;

Q.push(cnt);

}

if(v==target)

break;

tmp = nodes[top];

rotate(tmp.str);

v = cantor_hash(tmp.str);

if(!used[v]){

cnt++;

used[v] = true;

tmp.op = 'C';

tmp.hash = v;

tmp.pre = nodes[top].index;

tmp.index = cnt;

nodes[cnt] = tmp;

Q.push(cnt);

}

if(v==target)

break;

}

}

int main(){

int i;

ifstream fin("msquare.in");

ofstream fout("msquare.out");

for(i=0; i<8; ++i)

fin>>dest[i];

init();

target = cantor_hash(dest);

if(target == cantor_hash(nodes[0].str)){

fout<<0<<endl<<endl;

return 0 ;

}

bfs();

int count=-1, t=cnt;

while(t!=-1){

ops[++count] = nodes[t].op;

t = nodes[t].pre;

}

reverse(ops, ops+count);

fout<<count<<endl<<ops<<endl;

return 0;

}

posted on 2010-12-30 23:32 小阮阅读(258) 评论(0) 编辑收藏引用所属分类: USACO

只有注册用户登录后才能发表评论。


相关文章: USACO_MAR11 Spiral (螺旋矩阵, 模拟) USACO 6.1.2 A Rectangular Barn (最大子矩阵, DP) USACO 6.1.1 Postal Vans (哈密顿回路, 递推, 高精度计算) USACO 5.5.3 Two Five (DP) USACO 5.5.2 Hidden Passwords (后缀数组) USACO 5.5.1 Picture (离散化) USACO 5.4.5 TeleCowmunication (最小点割集, Dinic) USACO 5.4.4 Betsy's Tour (DFS+剪枝) USACO 5.4.3 Character Recognition (DP) USACO 5.4.2 Canada Tour (DP)

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理